|
|
|
|
|
|
|
|
CTK Exchange
pumpedcacti
Member since Dec-9-10
|
Dec-09-10, 08:09 AM (EST) |
|
"a wrong solution on this website"
|
I guess I'll start by being honest. I'm not a mathematician. In fact I'm barely a beginner. But, I have some skills. I was presented with a proof that neglected something. With that neglect the only option of someone without the proper background information, if it indeed exists, would be to assume that the information is correct. I must then prove it first. The problem I must determine is that there exists two powers of three that are a number factorable by a thousand apart, with the last three digits of each the same; equivelantly with the same remainder when divided by a thousand. What I have so far concluded is that the difference of the numbers n and m of 3^n and 3^m must be a number factorable by four. The reason is that 3 to the power 4 is 81, and any number 3^n can only be equivalent to 3^n+x except for a difference that is factorable by a 1000 when the last three digits between the two are the same, and that is only achievable when 3 to the power of x is 81 or factorable by 81, and that is only workable when x is factorable by 4, and so x must be such that x/4 is an integer. The reason 3 to the power of x must be factorable by 81 is that that is the lowest power of three that ends in one and all others can be factored by it. And, that is important because if the last three digits of 3^n and 3^m are to be equal, then the factor by which they are apart must end in 001, for #######aaa * only a number #####001 can equal ########aaa. So I must find a number factorable by 81 that ends in 001 to prove that there exists 3^n and 3^m that has a difference factorable by 1000 Once I do that then I can prove that there exists 3^n that ends with 001 So, apparently the way the solution is set up on https://www.cut-the-knot.org/pigeonhole/powerofthree.shtml#solution is wrong - it begs the question It tries assumes what it claims to prove; therefor it doesn't prove it. And, my way through the problem is to prove the very thing that it is supposed to prove but via a different route. They claim to have proved x, but I have to prove x before it can be verified. You see it'starts off by claiming that there are 2 numbers 3^n and 3^m that have the same remainder when divided by 1000 without proving it is possible. And, that is supposed to be the basis for the claim that there is a number 3^n that ends with 001; the problem is that I must know that a number 3^n ends in 001 before I can prove the first assertion, which is necessary for the second. You see x is supposed to prove y, but x isn't proved, and only when I have proved y will I have proved x. It's faulty notice that @ https://www.cut-the-knot.org/pigeonhole/powerofthree.shtml It says "solution" - and it is supposed to be a solution to "Prove that there exists a power of three that ends with 001" Follow the link to https://www.cut-the-knot.org/pigeonhole/powerofthree.shtml#solution And, you'll see what I mean. Thanks Shawn
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
alexb
Charter Member
2815 posts |
Dec-09-10, 08:26 AM (EST) |
|
1. "RE: a wrong solution on this website"
In response to message #0
|
>So I must find a number factorable by 81 that ends in 001 to >prove that >there exists 3^n and 3^m that has a difference factorable by >1000 >Once I do that then I can prove that there exists 3^n that >ends with 001 >So, apparently the way the solution is set up on >https://www.cut-the-knot.org/pigeonhole/powerofthree.shtml#solution >is wrong - it begs the question >It tries assumes what it claims to prove; therefor it >doesn't prove it. Forget for a moment about powers of three. I claim that among any 1001 integers there is at least one pair whose difference is divisible by 1000. Why? Because, all in all, there are only 1000 different remainders of division by 1000. Thus, among 1001 numbers there are bound to be at least two with the same remainder. This is the essence of the Pigeonhole principle. Now return to the powers of three. Take 1001 of them: 1, 3, 9, ..., 3<sup>1000</sup> Some two must have the difference divisible by 1000. Let these be 3<sup>n</sup> and 3<sup>m</sup>, with n > m. Then, as on the page, 3<sup>n</sup> - 3<sup>m</sup> is divisible by 1000. But 3<sup>n</sup> - 3<sup>m</sup> = 3<sup>m</sup>(3<sup>n-m</sup> - 1) and since gcd(3<sup>m</sup>, 1000) = 1, 1000 divides the second factor. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
pumpedcacti
Member since Dec-9-10
|
Dec-10-10, 08:23 AM (EST) |
|
2. "RE: a wrong solution on this website"
In response to message #1
|
Thanks for your reply. The pidgeonhole principle satisfies the first statement, and I understood the rest of the problem. I just made the mistake of not following the link "a related problem" just before the statement. In fairness, I was about to go to sleep when I looked at the solution. yup; 3^n - 3^m = 3^m(3^n-m - 1) because 3^n = 3^m(3^n-m), and "- 1" in 3^m(3^n-m - 1) is equal to 3^m. And, it's obvious that 3^m doesn't have a factor in common with 1000, simply because the only relevant factors that 3^m has that are under 501 are 3, 9, 27, 81, and 243. None of those is a factor of 1000. As such, 3^m is not divisible by 1000. So, since 3^n - 3^m by definition is divisible by 1000, it must be the case that (3^n-m - 1) is divisible by 1000. So, excluding the "-1" 3^n-m ends in 001. And, is equal to 3 to a power that is the difference between n and m; or 3^x(or 3^n) whateverAlso: The pidgeonhole principle must be true, and I'll show you that I understand it. Take a set of 1000 integers, each with the last 3 digits unique. Then add one more, and you must be duplicating one of them in terms of the last 3 digits. So, take 1000 numbers, each a power of 3, and then add one more; one must at that point duplicate one of the others in terms of the last 3 digits. So, when the duplicates are subtracted, the difference is the first digit(some non zero positive number) followed by three 0's(indicating that the last three digits are the same). So, it would follow that the difference is in that case divisible by 1000. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
alexb
Charter Member
2815 posts |
Dec-10-10, 08:26 AM (EST) |
|
3. "RE: a wrong solution on this website"
In response to message #2
|
>The pidgeonhole principle must be true, and I'll show you >that I understand it. Take a set of 1000 integers, each with >the last 3 digits unique. Yes, but this is the worst case scenario. Duplicates may be already in, so you say, "Assume the first 1000 are all different, then ..." >Then add one more, and you must be >duplicating one of them in terms of the last 3 digits. So, >take 1000 numbers, each a power of 3, and then add one more; >one must at that point duplicate one of the others in terms >of the last 3 digits. So, when the duplicates are >subtracted, the difference is the first digit'some non zero >positive number) followed by three 0's(indicating that the >last three digits are the same). So, it would follow that >the difference is in that case divisible by 1000. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
|
You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Copyright © 1966-2016 Alexander Bogomolny
|
|