Each USAMO has 5 question in various levels for 3.5 hours. I agree with both of you, I really doubt, any one could solve this problem during the exam time.
The Chinese remainder Theorem is the first thing coming into my mind. However, it is too hard to be done in 90 minutes... The first claim is hard to find out.....Although I was thinking about some similar things..........www.ddhw.com
Well, I think this kind of problem should still be welcomed...
So if fully written out, the standard solution is shorter than mine. But I really do not see any one who is not a trained number theorist can come up with that solution in a reasonable amount of time.www.ddhw.com
Thanks for your concern. I am not upset. :) I no longer care about learning new skills in number theory or anywhere. Instead I do the problems as a way for brain excercise. :Dwww.ddhw.com
I agree with you that they must be crazy to give such difficult problem as a test question, and I am very sorry I did not read the solution carefully before I posted the problem. (So I am crazy too , although I am not on purpose.) I thought a test problem would not be too difficult for people like you. You have done a great job. I don't understand how people could give the solution without a computer. I think through your hard and creative work, you could master these skills in number theory better, hopefully you would not regret having spent time on this problem.
Let me post their solution here,
Claim1: For any n, at least one of the following is true:
a)n=1(mod2)
b)n=1(mod3)
c)n=2(mod4)
d)n=4(mod8)
e)n=0(mod12)
f)n=8(mod24)
Pf: If n is odd, a) is true;
if 2 divides n but 4 not, then c) is true;
if 4 divides n but 8 not, then d) is true;www.ddhw.com
consider n=8m,
if m=3k, then e) is true
if m=3k+1,then f) is true
if m=3k+2, then b) is true//
Notice:
2^2=1(mod3)
2^3=1(mod7)
2^4=1(mod5)
2^8=1(mod17)
2^12=1(mod13)
2^24=1(mod 241)
Therefore
case a) n=1(mod2) or n=2m+1, then k*2^n+1=k*2^(2m+1)+1=2k*2^2m+1=2k+1(mod3)
Similarly, we have
case b) K*2^n+1=2k+1(mod7)www.ddhw.com
case c) k*2^n+1=4k+1(mod5)
case d) k*2^n+1=16k+1(mod17)
case e) k*2^n+1=k+1(mod13)
case f) k*2^n+1=256k+1(mod241)
Thus, if k satisfies all the followings, then k*2^n+1 is divisible by at least one of 3,7,5,17,13,241, therefore k*2^n+1 is not prime.
2k+1=0(mod3)
2k+1=0(mod7)
4k+1=0(mod5)
16k+1=0(mod17)
k+1=0(mod13)
256k+1=0(mod241)
www.ddhw.com
But those congruences are equivalent to the followings:
k=1(mod3)
k=3(mod7)
k=1(mod5)
k=1(mod17)
k=-1(mod13)
k=16(mod241)
Since all 3,7,5,17,13,241 are primes, according to the Chinese Remainder Theorem, there must be solutions. Actually, k=1207426+5592405m
They both cover all n. Now we can use the Chinese remainder theorem to find the k with proper remainders. But that would take another program and I am in no mood to do that.
Are you telling me this is the only way to solve it? They must be crazy to give a problem like this! Even if you know what to do right away, the calculation would take several hours! www.ddhw.com
I have an idea. But there seems to be too much calculation to do during a competition. It is like this:www.ddhw.com
When k mod 3 != 0, 1/2 of k*2^n + 1 is divisible by 3. When k mod 5 != 0, 1/4 of them is divisible by 5. For 7, when k mod 7 != 3, 5, or 6, 1/3 of them is divisible by 7. Together they can cover about 5/6 of n. As we go through the prime numbers we should be able to find a group of numbers to cover all n. But I went up to 41 and was not yet successful. Might need to write a program to do it.
Probably some results in number theory can give a non constructive proof.
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2005-2-18 21:03:04
收藏
分享
支持
反对
置顶卡
千斤顶
楼主