(1982年 美 国 奥 赛 题 ) 证 明 存 在 一 个 正 整 数 k

fzy

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. www.ddhw.com

fzy

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/24www.ddhw.com 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! www.ddhw.com

fzy

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