I have an idea. But there seems to be too much calculation to do during a competition. It is like this: 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. |
Use the Chinese Remain Theorem. It IS very difficult, I doubt whether any people could solve it during the exam time. |
I ran my program for all prime numbers < 1000, and the only solutions I found are: 3 -> 1/2 5 -> 1/4 7 -> 1/3 13 -> 1/12 17 -> 1/8 241 ->1/24 and 3 -> 1/2 5 -> 1/4 7 -> 1/3 13 -> 1/12 17 -> 1/8 97 -> 1/48 257 -> 1/16 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! |
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; 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) 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) 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 |
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. 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. :D |
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.......... Well, I think this kind of problem should still be welcomed... |
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. |
| 欢迎光临 珍珠湾ART (http://art.zhenzhubay.com/) | Powered by Discuz! X3 |