9||0|141|0| 0|0|0|||||Cantor Set|Paolo Di Muccio|1|12:14:08|02/09/2011|Do you really need compactness in the first proof that C - C %3D %5B0%2C1%5D%3F%0D%0A%0D%0AIt seems to me that %7BBi%7D and %7BCi%7D converge on their own...%0D%0A%0D%0AReference%3A A. Bogomolny%2C Difference of two Cantor sets from Interactive Mathematics Miscellany and Puzzles%0D%0Ahttp%3A%2F%2Fwww.cut-the-knot.org%2Fdo_you_know%2Fcantor3.shtml%2C Accessed 09 February 2011%0D%0A 1|1|0|||||RE%3A Cantor Set|alexb||12:29:51|02/09/2011|%3E It seems to me that %7BBi%7D and %7BCi%7D converge on their own...%0D%0A%0D%0AWe actually know nothing of the behavior of %7BBi%7D and %7BCi%7D%2C except that Ai %3D Bi - Ci. While Ai does have a limit%2C Bi and Ci may a priori oscilate any other way. They become close to each other%2C yes. But they both may grow in magnitude%2C at least in principle.%0D%0A%0D%0A 2|2|1|||||RE%3A Cantor Set|Paolo Di Muccio|1|16:22:16|02/12/2011|I%27m sorry to bother again. In the example%3A %0D%0A%0D%0A%22As an example%2C for a %3D 0.1202112%2C we have successively%0D%0A%0D%0A0.1 %3D 0.2 - 0.0222... %0D%0A0.12 %3D 0.22 - 0.0222... %0D%0A0.120 %3D 0.220 - 0.0222... %0D%0A0.1202 %3D 0.2202 - 0.0222... %0D%0A0.12021 %3D 0.2202 - 0.02222 %0D%0A0.120211 %3D 0.220202 - 0.022220222... %0D%0A0.1202112 %3D 0.2202022 - 0.022220222... %22%0D%0A%0D%0Aboth %7BBi%7D and %7BCi%7D converge%2C if I am not mistaken%2C and I cannot think of an example where this is not the case%21 %3A-%28 3|3|2|||||RE%3A Cantor Set|alexb||16:23:08|02/12/2011|So%2C prove that this is always the case. 4|2|1|||||RE%3A Cantor Set|mr_homm||23:23:38|02/12/2011|This has started me thinking about variations on the given proof %231.%0D%0A%0D%0AWe want to solve A %3D B - C with A in %26l%3B0%2C 1%26r%3B and B%2C C in the Cantor set. As in the given proof%2C A%2C B%2C and C are written as ternary strings%2C with B and C free of the digit 1. Let%27s think of the problem as A %2B C %3D B%2C set up in the format of the usual grade-school arithmetic exercise with sums and carries at each digit location.%0D%0A%0D%0ANow the basic limitation of the given proof is that the carry value propagates from right to left%2C so that one must have a starting point for the calculation at the right end of the digit sequence. Hence only finite digit sequences can be constructed%2C and topological arguments are needed to obtain the solution for the rest.%0D%0A%0D%0AThis can be avoided by the following trick borrowed from computer science%3A in designing an algorithm for a recursive calculation one tries to reformulate the problem to make as much of it as possible non-recursive%2C leaving only a minimal core of recursion. Let us then try to split the calculation into a recursive step which computes ONLY THE CARRY%2C and a non-recursive step which then specifies the solution. %0D%0A%0D%0AAt each digit location%2C one of the following 6 possibilities holds%2C where i %3D the carry into this digit%2C o %3D the carry out to the left neighbor digit%2C and x is a free choice of 0 or 2%3A%0D%0A%5Bcode%5D%0D%0Ao i%09%7C%090 0%09%091 1%09%091 0%09%090 1%09%090 0%09%091 1%0D%0A a%09%7C%09 0%09%09 0%09%09 1%09%09 1%09%09 2%09%09 2%0D%0A %2B c%09%7C%09 x%09%09 2%09%09 2%09%09 0%09%09 0%09%09 x%0D%0A ---%09%7C%09 ---%09%09 ---%09%09 ---%09%09 ---%09%09 ---%09%09 ---%0D%0A %3D b%09%7C%09 x%09%09 0%09%09 0%09%09 2%09%09 2%09%09 x%0D%0A%5B%2Fcode%5D%0D%0A%0D%0AWhen a %3D 0 or 2%2C i %3D o%2C and when a %3D 1%2C i %3D %7Eo%2C and both of these relations are symmetrical in i and o. It is therefore clear that the carry can be propagated from left to right instead of right to left. Simply start with i%280%29 %3D 0 %28so that the resulting number B will not exceed 1%29%2C and move to the right through the digits of A%2C toggling i%28n%29 whenever a%28n%29 %3D 1. This constructs a unique %28binary%29 carry string I for any A in %26l%3B0%2C 1%26r%3B.%0D%0A%0D%0AWith the carry string available%2C the computation of each digit of B and C is independent and can be carried out non-recursively. Specifically%2C let D %3D A %2B I mod 3 %28where the addition and mod 3 reduction is separate for each digit%29. Then define C by c%28n%29 %3D2%2A%28d%28n%29 %3D%3D 1%29 and B by b%28n%29 %3D 2%2A%28d%28n%29 %3D%3D 2%29. B and C are then the desired elements of the Cantor set.%0D%0A%0D%0AB and C are also the SMALLEST pair that works%2C since we have chosen zero for every value of x. If we further define E by e%28n%29 %3D x%2A%28d%28n%29 %3D%3D 0%29%2C where each x is 0 or 2 arbitrarily%2C then B%27 %3D B%2BE and C%27 %3D C%2BE is another pair of solutions. Since I%2C B%2C and C are completely determined by A%2C the only variation possible is in E%3B hence the set of all B%27%2C C%27 is the complete set of solutions to the problem. %0D%0A%0D%0AFurther%2C the arbitrary choices in E can be described by choosing a binary string X in %26l%3B0%2C 1%26r%3B and letting 2%2Ax%28n%29 be the nth digit choice made in E %28not the nth digit of E%2C but the nth occurance of d %3D 0%29. Then each X corresponds to a solution B%27%2C C%27 and the full set of solutions is indexed by %26l%3B0%2C 1%26r%3B if there are infinitely many 0 digits in D. If D has only finitely many 0 digits%2C then of course there are finitely many choices. From this%2C we have the interesting corollary%3A%0D%0A%0D%0AFor every A in %26l%3B0%2C 1%26r%3B%2C the number of distinct pairs of Cantor set members satisfying A %3D B - C is 2%5Ez%2C where z is the number of occurances of the digit 0 in D. This is true even if z is infinite%2C since 2%5Ecard%28N%29 %3D card%28%26l%3B0%2C 1%26r%3B%29.%0D%0A%0D%0AThank you for this very interesting problem. I hope this approach is to your liking.%0D%0A%0D%0A--Stuart Anderson 5|3|4|||||RE%3A Cantor Set|alexb||12:15:55|02/13/2011|Stuart%2C%0D%0A%0D%0A%3E Thank you for this very interesting problem.%0D%0A%0D%0AYou made the problem interesting. Thank you for the very enlightening solution. 6|4|5|||||RE%3A Cantor Set|mr_homm||15:57:49|02/16/2011|%3E Thank you for the very enlightening solution.%0D%0A%0D%0AGlad you enjoyed it. I%27ve been thinking further%2C and it seems that Paolo%27s point is well taken. The algorithm you use to generate the digit sequences never changes a digit once it has been set. Hence if one wants to think of the finite digit sequences as partial sums of the finished infinite sequence%2C one may do so. %0D%0A%0D%0AThen for any N %3E 0%2C and for any m and k both %3E N%2C the partial sums 0. b_0 b_1 ... b_k and 0. b_0 b_1 ... b_m agree to at least N places%2C and so differ by at most 3%5E%28-N%29. But this clearly shows that the sequence is a Cauchy sequence %28for any epsilon %3E 0%2C simply choose N so 3%5E%28-N%29 %3C epsilon%29%2C hence it converges independent of any compactness assumption. Of course the same applies to %7Bc_n%7D as well.%0D%0A%0D%0ASo I agree that topology must come into the proof in order to reach the infinite digit sequences%2C but only via the Cauchy criterion%3B compactness appears unnecessary. Or have I jumped to a conclusion somewhere%3F%0D%0A%0D%0A--Stuart Anderson 7|5|6|||||RE%3A Cantor Set|alexb||08:49:22|02/17/2011|Oh%2C yes.%0D%0A%0D%0AAt the time of writing I assumed that there are many ways a number can be a difference of two Cantor%27s terms - which you actually showed and which is more or less clear from the diagram in the second proof.%0D%0A%0D%0AWhat I missed to observe or to capitalize on was that the algorithm in the first proof does not change the already established established digits. 8|6|7|||||RE%3A Cantor Set|mr_homm||11:41:28|02/17/2011|I see you%27ve added my proof to the Cantor set page. It looks much nicer now that it has proper formatting. Thank you%21%0D%0A%0D%0A--Stuart 9|7|8|||||RE%3A Cantor Set|alexb||11:46:42|02/18/2011|Thank you%2C Stuart.