暑假挑戰50

turnX

原文由M.N.M. 於 07-7-15 05:58 PM 發表
9.在小於10^4的正整數中，有多少個正整數n，使(2^n)-(n^2)被7整除

此題使用同餘
2^n-n^2 mod 7 = 0
=> [2^n mod 7]-[n^2 mod 7] = 0

觀察 2^n mod 7 之餘數的循環為 2,4,1 (每3個一循環)
觀察 n^2 mod 7 之餘數的循環為1,4,2,2,4,1,0 (每7個一循環)

取最小公倍數為一週期 lcm(3,7)=21
比對
1,4,2,2,4,1,0 | 1,4,2,2,4,1,0 | 1,4,2,2,4,1,0
2,4,1,2,4,1,2 | 4,1,2,4,1,2,4 | 1,2,4,1,2,4,1

在一週期中有 6 個數一樣 ,表示每21個連續正整數就有6個可使式子被7整除

21x<10000
x<476.xxx (有476個循環)

476*21=9996 (最後還差3個數)
1,4,2
2,4,1
最後3個數只有一個符合

所以有 476*6+1 個數會符合在小於10^4的正整數中
476*6+1 = 2857

Ans:2857

[ 本文最後由 turnX 於 07-7-17 07:10 PM 編輯 ]

‧幻星〞

32.分解因式:[(b-c)^6]+[(c-a)^6]+[(a-b)^6]-9[(a-b)^2][(b-c)^2][(c-a)^2]-2[(a-b)^3][(a-c)^3]-2[(b-c)^3][(b-a)^3]-2[(c-a)^3][(c-b)^3]

題目=(b-c)^6+(c-a)^6+(a-b)^6-3(a-b)^2*(b-c)^2*(c-a)^2-6[(a-b)(b-c)(c-a)]^2-2[(a-b)(a-c)]^3-2[(b-c)(b-a)]^3-2[(c-a)(c-b)]^3
=[(a-b)^2+(b-c)^2+(c-a)^2][(a-b)^4+(b-c)^4+(c-a)^4-(a-b)^2*(b-c)^2-(b-c)^2*(c-a)^2-(a-b)^2*(c-a)^2]-2{[(a-b)(a-c)]^3+[(b-c)(b-a)]^3+[(c-a)(c-b)]^3-3(a-b)(a-c)(b-c)(b-a)(c-a)(c-b)}
=2(a^2+b^2+c^2-ab-bc-ac)*1/2*{[(a-b)^2-(b-c)^2]+[(b-c)^2-(c-a)^2]+[(c-a)^2-(a-b)^2]}-2[(a-c)(a-b)+(b-c)(b-a)+(c-a)(c-b)]{[(a-c)(a-b)]^2+[(b-c)(b-a)]^2+[(c-a)(c-b)]^2-(a-b)^2(b-c)(c-a)-(a-b)(b-c)^2(c-a)-(a-b)(b-c)(c-a)^2}
=(a^2+b^2+c^2-ab-bc-ac){[(a-b)^2-(b-c)^2]+[(b-c)^2-(c-a)^2]+[(c-a)^2-(a-b)^2]}-2(a^2+b^2+c^2-ab-bc-ac)*1/2*{[(a-c)^2(a-b)^2-(b-c)^2(b-a)^2]+[(b-a)^2(b-c)^2-(c-a)^2(c-b)^2]+[(c-a)^2(c-b)^2-(a-b)^2(a-c)^2]}
=2(a^2+b^2+c^2-ab-bc-ac)^3-2(a^2+b^2+c^2-ab-bc-ac)^3
=0

瘋掉~~~

[ 本文最後由 ‧幻星〞 於 07-7-19 10:40 PM 編輯 ]

~冠~

1.
Obviously, n must be an even number. (if n>1)
but, n can't have an odd factor,if it has an odd factor k
let n be (2^m)k
then n^n+1=(2^m)k^ (2^m)k+1 has a factor(2^m+1)>1
so, n=2^2 or 4^4 or 8^8, 16^16>10^19 (Use log)
but 8^8+1=(2^3)^8=(2^8)^3+1=(2^8+1)k
so, n=2 and 4
2^2+1=5, 4^4+1=257, 1^2+1=2.

[ 本文最後由 ~冠~ 於 07-7-18 12:00 PM 編輯 ]

‧幻星〞

12.設數列<a_n>，其中a_n表最接近√a_n之正整數值，試求Σ(n=1~2003) a_n=?

設<a_n>=K
(K+0.5)^2-(K-0.5)^2=2K
所以有2K個n會使得<a_n>=K
其總和為2K^2
2*1加到45=1980最接近2003又比2003小
2003-1980=23
有23個46
45*(45+1)*(2*45+1)/3=62790
62790+23*46=63848

A：63848


19.在一條直線上有2n個點，相鄰兩個點間距離為1，某人從第一個點開始跳到其他點，跳了2n次後回到第1個點，這2n次跳躍將這2n個點全部都到達了，問怎樣跳才能使他的路程最遠?

化成絕對值
題目就變成
|a1-a2|+|a2-a3|+...|a(2n-1)-an|+|an-a1|
將1~2n填入a使上式最大
上式最大不會超過(n+n+1+...+2n)-(1+2+...+n)=1+2+..+n
所以只要讓2n個數的差都不一樣就好了
所以只要1,2n,2,2n-1,3,2n-2...,n,n+1這樣跳

[ 本文最後由 ‧幻星〞 於 07-7-17 10:34 PM 編輯 ]

turnX

19.在一條直線上有2n個點，相鄰兩個點間距離為1，某人從第一個點開始跳到其他點，跳了2n次後回到第1個點，這2n次跳躍將這2n個點全部都到達了，問怎樣跳才能使他的路程最遠?

題目等價於以下之命題

a1,a2,...,a(2n-2),a(2n-1) 為 2~2n之排列
find max{ |1-a1|+|a1-a2|+|a2-a3|+...+|a(2n-2)-a(2n-1)|+|a(2n-1)-1| }

或是

找出最長之HC(這條HC必須以1為起點) 於 K(2n)之圖, ( K(2n)為一完全圖,完全圖即每點間都有路徑相連 )

最長路徑跳法為

1 -> 2n-1 -> 2 -> 2n-2 -> 3 -> 2n-3 ->...-> n -> 2n -> 1

證明....缺! XD

[ 本文最後由 turnX 於 07-7-17 11:17 PM 編輯 ]

~冠~

18.
4x_2=6 (mod26)
x_2=8 or 21
if x_2=8, x_1=9
x_4=7
x_3=6
6x_4=42 42+x_5=9 (mod26) =>x_5=20
so, x_1,x_2,x_3,x_4,x_5=>  17,8,6,7,19
The word is RIGHT

turnX

18.有一個英文單字由5個字母組成，如果將26個英文字母a，b，c，...，y，z按順序對應0到25這26個整數，那麼這個單字中的5個字母對應的整數按從左到右的順序分別為x_1，x_2，x_3，x_4，x_5。已知(x_1)+3(x_2)，4(x_2)，(x_3)+2(x_4)，5(x_4)，6(x_4)+(x_5)除以26所得的餘數分別為15，6，20，9，9。則該英文單字為何?

可以整理出五條式子

[(x_1)+3(x_2)] mod 26 = 15 ---(1)
[4(x_2)] mod 26 = 6 ---(2)
[(x_3)+2(x_4)] mod 26 = 20 ---(3)
[5(x_4)] mod 26 = 9 ---(4)
[6(x_4)+(x_5)] mod 26 = 9 ---(5)

先處理第(4)式
[5(x_4)] mod 26 = 9
(26個字母中,只有h符合 h=7)
x_4=7

再來處理第(5)式
[6(x_4)+(x_5)] mod 26 = 9
=> [42+(x_5)] mod 26 = 9
42+x_5之範圍為( 42~67 ) 而其中符合者只有61
x_5=61-42=19 (19為t)

再來處理第(3)式
[(x_3)+14] mod 26 = 20

x_3+14的範圍為(14~39) 而其中符合者只有 20
所以x_3=20-14=6   (6為g)

再來處理第(2)式
[4(x_2)] mod 26 = 6
符合者有兩個 i(8) or v(21)

如果 x_2=8 也就是i 解第(1)式
[x_1+24] mod 26 = 15
x1+24的範圍為(24~49) 而其中符合者只有41
x_1=41-24=17 (17為r)

如果 x_2=21 也就是v 解第(1)式
[x_1+63] mod 26 = 15
=> [x_1+11] mod 26 = 15
x1+11的範圍為(11~36) 而其中符合者只有15
x1=15-11=4 (4為e)

所以,所有的組合有 right 和 evght 兩個
但 evght 不是單字

Ans:right

~冠~

30.
ax^2+bx+c為一二次函數,如果頂點不在[0,1]區間內或頂點在x=1上,
則在此區間內為嚴格遞增或嚴格遞減.明顯-1<=c<=1.
考慮嚴格遞增時,|a+b+c|=1 (-b>=2a)
為使值最大,所以|c|=1, 明顯c=-1.
因此a+b<=2, 因此a>=-2,選a=-2, b=4.
y=-2x^2+4x-1符合本題題意.

嚴格遞減時,b<=0,
令c=1, a+b<=-2 但a和b同時<0,
所以|a|+|b|=|a+b|=2 此時他的最大值<遞增時.

如過頂點在[0,1]內,
開口越小則a越大,最小的情況便是當頂點在(1/2,1)or(1/2,-1)
且f(1)=f(0)=-1orf(1)=f(0)=1.
第一個情況的函數為-8x^2+8x-1
第二個情況的函數為8x^2-8x+1
|8|+|-8|+|1|=17
.....17(MAX)

~冠~

40.
(n>1)
|2^7-5^3|=3
We pridict 3 is the min value.
So, we're going to prove that 2^m-5^n can't be 1 or -1.
(Obviously, the value is an odd number)

Case1.
2^m-5^n=1,=>2^m-1=5^n
We discovered that 2^(4k)-1=0 (mod5)
(2^k-1)(2^k+1)(4^K+1)=2^(4k)-1
but gcd(m-1,m+1)=1or2, so both of them cna't be divided by 5.
That shows 2^m-5^n=1 is impossible.

Case2.
2^m-5^n=-1=>2^m+1=5^n
We discovered that 5^n-1=0(mod2)
No matter what natural number n is.
But, if n is an even number, we can prove it as Case1's method.
If n is an odd number,
5^n-1=(5-1)(5^(n-1)+5^(n-2)+....+1)
Unfortunately, 5^(n-1)+5^(n-2)+....+1 is an odd number.
That shows 2^m+1=5^n is impossible.

Above all, we probe that the value can be neither 1 nor -1.
So, the min is 3.

[ 本文最後由 ~冠~ 於 07-7-18 03:43 AM 編輯 ]

~冠~

7.
Well, S1 should be 441, (I've seen this problem before)
Let BC=a, AC=b
(a+b)21=ab, and the height h based in AB is ab/sqrt(a^2+b^2)
so, h=21(a+b)/sqrt((a+b)^2-42(a+b))
Beacuse S2 is 440,
Let a+b=m, we have:
440^(1/2)/(m^2-42m)^(1/2)=(((21m)/(m^2-42m)^(1/2))-(440)^(1/2))/((21m)/(m^2-42m)^(1/2))
we can solve this equation,
Thus we get m=462.
so m=a+b=AC+BC=462.