A similar problem was considered in Kvant journal in 1977 N 3 (in Russian): http://kvant.mccme.ru/1977/03/mnogo_bitov_iz_nichego.htm In that problem the logicians A and B are given respectively the sum and the product of two unknown positive numbers whose sum is below 100, and their dialog goes as follows: A: I cannot determine what the numbers are. B: I knew that you cannot determine them. A: Then I know these numbers. B: Then I know them as well.

This problem is intriguing! Number the sentences in conversation: <<1>> B: I can't tell what the numbers are. <<2>> A: I can't tell what the numbers are. <<3>> B: I can't tell what the numbers are. <<4>> A: I can't tell what the numbers are. <<5>> B: I can't tell what the numbers are. <<6>> A: I can't tell what the numbers are. <<7>> B: Now I can tell what the numbers are. Denote the sum S and sum of squares N. S-list will be a list of all possible sums a + b, N-list a list of all possible sums of squares a^2 + b^2. Initially, the S-list contains all positive integers >1, N-list all positive integers expressible as sum of two positive integer squares. The section <<i>> below describes the information gained after the line <<i>> in the conversation was spoken. <<1>> N is not expressible as the sum of positive integer squares uniquely. N-list is correspondingly adjusted (numbers expressible as sum of two positive integer squares uniquely are thrown out). S-list is adjusted – sums are thrown out, that don’t allow for summands a, b, such that a^2 + b^2 is on the current N-list. <<2>> S allows for more values of a, b (a + b = S), such that a^2 + b^2 belongs to the N-list. S-list is adjusted (sums are deleted not allowing for more values of a, b (a + b = the sum), such that a^2 + b^2 belongs to the N-list). <<3>> N allows for more values of a, b (a^2 + b^2 = N), such that a + b is on the S-list. Those integers that don’t are deleted from the N-list. <<4>> S allows for more values of a, b, such that a^2 + b^2 belongs to the N-list. Those integers that don’t are deleted from the S-list. <<5>> N allows for more values of a, b, such that a + b belongs to the S-list. Those integers that don’t are deleted from the N-list. <<6>> S allows for more values of a, b, such that a^2 + b^2 belongs to the N-list. Those integers that don’t are deleted from the S-list. <<7>> At this moment there is only one pair of positive integers a, b, such that a + b is on the S-list and a^2 + b^2 = N. If N-list contains more values, they need to be checked to see if they allow for unique solution. If some bounds are imposed on a,b, I guess the solution could be found by computer or manual deleting from the S- and N-list. I haven't really thought beyond this outline yet, at this moment solving the problem in full generality seems difficult... I'd love to see the intended solution.

Peter wrote: a) Two positive integers are chosen. The sum is revealed to logician $A$, and the sum of squares is revealed to logician $B$. Both $A$ and $B$ are given this information and the information contained in this sentence. The conversation between $A$ and $B$ goes as follows: $B$ starts B: ` I can't tell what they are.' A: ` I can't tell what they are.' B: ` I can't tell what they are.' A: ` I can't tell what they are.' B: ` I can't tell what they are.' A: ` I can't tell what they are.' B: ` Now I can tell what they are.' What are the two numbers? Let $A_i(s)$ be the set of candidate pairs of integers that $A$ can derive after the $i$-th claim of $B$, assuming that $A$ is given the sum $s$. Similarly, let $B_i(t)$ be the set of candidate pairs of integers that $B$ can derive after the $i$-th claim of $A$, assuming that $B$ is given the sum of squares $t$. Clearly, we have \[A_0(s) = \{ [x,y]\,:\,1\leq x\leq y,\,x+y=s \}\] \[B_0(t) = \{ [x,y]\,:\,1\leq x\leq y,\,x^2+y^2=t \}\] The $i$-th claim B: ` I can't tell what they are.' basically means that $|B_{i-1}(t)|>1$, while the $i$-th claim A: ` I can't tell what they are.' means that $|A_i(s)|>1$. Therefore, we have the following recurrence: \[A_{i+1}(s) = \{ [x,y]\in A_i(s)\,:\,|B_i(x^2+y^2)| > 1\}\] \[B_{i+1}(t) = \{ [x,y]\in B_i(t)\,:\,|A_{i+1}(x+y)|> 1\}\] The whole dialog means that in the sequences \[A_0(s)\supset A_1(s) \supset A_2(s) \supset A_3(s)\] \[B_0(t)\supset B_1(t)\supset B_2(t)\supset B_3(t)\] all sets contain more than one element, except for $B_3(t)$ which contains a single element. So far, I've found only one such pair of integers $[8,9]$, which results in the following sequence of sets: \[A_0(8+9) = \{ [1, 16], [2, 15], [3, 14], [4, 13], [5, 12], [6, 11], [7, 10], [8, 9] \}\] \[A_1(8+9) = A_2(8+9) = A_3(8+9) = \{ [3, 14], [4, 13], [8, 9] \}\] \[B_0(8^2+9^2) = B_1(8^2+9^2) = B_2(8^2+9^2) = \{ [1, 12], [8, 9] \}\] \[B_3(8^2+9^2) = \{ [8, 9] \}\] It remains unclear how to prove that there are no other suitable pairs.

Below is my attempt to prove that $[8,9]$ is the only solution to the original problem. My proof still relies on a certain unproved statement which, however, sounds plausible from heuristic perspective and can be studied independently of the original problem. maxal wrote: Therefore, we have the following recurrence: \[A_{i+1}(s) = \{ [x,y]\in A_i(s)\,:\,|B_i(x^2+y^2)| > 1\}\] \[B_{i+1}(t) = \{ [x,y]\in B_i(t)\,:\,|A_{i+1}(x+y)|> 1\}\] These recurrences can be given a different interpretation: a pair $[x,x']$ from $A_i(x+x')$ belongs to $A_{i+1}(x+x')$ iff there exists a pair $[y,y']\ne [x,x']$ such that $[y,y']\in B_i(x^2+x'^2)$ (in particular, $x^2+x'^2=y^2+y'^2$). Similarly, a pair $[x,x']$ from $B_i(x^2+x'^2)$ belongs to $B_{i+1}(x^2+x'^2)$ iff there exists a pair $[y,y']\ne [x,x']$ such that $[y,y']\in A_{i+1}(x+x')$ (in particular, $x+x'=y+y'$). Call such a pair $[y,y']$ a certificate for the membership $[x,x']\in A_{i+1}(x+x')$ or $[x,x']\in B_{i+1}(x^2+x'^2)$, respectively. For the only element $[b_3,b'_3]\in B_3(t)$, there exists a certificate $[a_3,a'_3]\in A_3(b_3+b_3')$, for which there exists a certificate $[b_2,b'_2]\in B_2(a_3^2+a'_3^2)$, for which there exists a certificate $[a_2,a'_2]\in A_2(b_2+b'_2)$, and so on, ending up with the certificate $[b_0,b'_0]\in B_0(a_1^2+a'_1^2)$. That is, we have a chain of certificates: \[[b_3,b'_3]\rightarrow [a_3,a'_3] \Rightarrow [b_2,b'_2] \rightarrow [a_2,a'_2] \Rightarrow [b_1,b'_1] \rightarrow [a_1,a'_1] \Rightarrow [b_0,b'_0]\] where $\rightarrow$ connect pairs with equal sums, $\Rightarrow$ connect pairs with equal sums of squares, and no two adjacent pairs are equal. Since $|B_2(t)|>1$, there exists an element $[c_2,c'_2]\in B_2(t)$ such that $[c_2,c_2']\ne [b_3,b'_3]$ with its own chain of certificates: \[[c_2,c'_2]\rightarrow [d_2,d'_2] \Rightarrow [c_1,c'_1] \rightarrow [d_1,d'_1] \Rightarrow [c_0,c'_0]\] but since $[c_2,c'_2]\not\in B_3(t)$, it is impossible to extend this chain of certificates into \[[c_2,c'_2]\rightarrow [d_2,d'_2] \Rightarrow [c_1,c'_1] \rightarrow [d_1,d'_1] \Rightarrow [c_0,c'_0] \rightarrow [j,j'] \Rightarrow [k,k'].\] In other words, this means that for every representation of the number $m=c_0+c'_0$ as the sum of two positive integers $m=j+j'$, $j\leq j'$, the number $j^2+j'^2$ has an unique unordered representation as the sum of squares of two positive integers, with exacty one exception $[j,j']=[c_0,c'_0]$ (since $c_0^2+c'_0^2=d_1^2+d'_1^2$). Here comes the unproved statement that such integers $m$ (I've exhaustively tested all $m\leq 10^5$) are limited to the set: \[ \{ 8, 9, 10, 15 \}\] with the exceptional pairs $[c_0,c'_0] = [1,7], [1,8], [5,5], [5,10]$, respectively. They correspond to $[d_1,d'_1] = [5,5], [4,7], [1,7], [2,11]$, respectively. So, we can unroll back the possible elements in the certificate chain for $[c_2,c'_2]\in B_2(t)$: \[[d_1,d'_1] \in \{ [5,5], [4,7], [1,7], [2,11] \}\] \[[c_1,c'_1] \in \{ [1, 10], [1, 12], [1, 9], [2, 6], [2, 8], [2, 9], [3, 10], [3, 5], [3, 7], [3, 8], [4, 4], [4, 6], [4, 9], [5, 6], [5, 8], [6, 7] \}\] \[[d_2,d'_2] \in \{ [2, 9], [6, 7], [8, 9] \}\] \[[c_2,c'_2] \in \{ [1, 10], [1, 12], [1, 16], [2, 11], [2, 15], [3, 10], [3, 14], [3, 8], [4, 13], [4, 7], [4, 9], [5, 12], [5, 6], [5, 8], [6, 11], [7, 10] \} \] and since $[c_2,c'_2]$ and $[b_3,b'_3]$ both belong to $B_2(t)$, we have $b_3^2 + b_3'^2 = c_2^2 + c'_2^2$ and thus \[[b_3,b'_3] \in \{ [1, 8], [5, 10], [6, 13], [8, 11], [8, 9] \}. \] However, it is easy to check that \[B_3(1^2+8^2) = B_3(5^2+10^2) = \emptyset\] \[B_3(6^2+13^2) = \{ [3,14], [6,13] \}\] \[B_3(8^2+11^2) = \{ [4,13], [8,11] \}\] \[B_3(8^2+9^2) = \{ [8,9] \}\] out of which only the last satisfies the requirement $|B_3(t)|=1$. This consideration unambiguously derives the pair $[8,9]$ as the solution (under the assumption of yet unproved claim mentioned above).

I thought of this way: Cant=0 in binary and can=1 therfore the code becomes 1000000=8*8 and from the opposit side =0000001=1 there fore no,s are 0,8

a) Let's define a binary relation on the natural numbers as $a\rightarrow b$ iff there exists natural numbers $u,v$ with $a =u+v$ and $b = u^2 + v^2$. We'll use the notations $a\rightarrow b$ and $b\leftarrow a$ interchangeably. Note that every un-ordered pair of natural numbers $\{u,v\}$ can be uniquely identified by another ordered pair $(a,b)$ of natural numbers satisfying $a\rightarrow b$. In other words, the relation $a\rightarrow b$ is asserting that the pair of information available to the logicians is consistent. We will now generalize this notation with a parameter. Let $a_{\overrightarrow{k}} b$ denote that $(a,b)$ is consistent given that the logicians have exchanged their "I can't tell" assertions (at least) $k$ times (starting with B). The case $k=0$ is the special case above, the state before any assertions were made, i.e. $a\rightarrow b \iff a_{\overrightarrow{0}} b$. For example $3_{\overrightarrow{0}} 5$, but $3\not _{\overrightarrow{1}} 5$ since 5 can be written as sum of squares in an unique way and B would know the answer on his first question if this pair was indeed the chosen one. On the other hand $9_{\overrightarrow{1}} 65$ is true since B wouldn't be able to distinguish between the initial cases $9\rightarrow 65$ and $11\rightarrow 65$. However $9_{\overrightarrow{2}} 65$ is false because of all the ways of writing $9$ as sum of natural numbers, only $(8,1)$ admits a relation of the form $8^2+1^2 = 7^2 + 4^2$. Hence $(9,65)$ cannot be the initial pieces of information if the logicians exchange "I can't tell" twice. Note that, we can express the above reasoning in the following assertions: \[\forall \text{ even } k, \ a_{\overrightarrow{k+1}} b\iff \exists a' \neq a, a_{\overrightarrow{k}} b _{\overleftarrow{k}} a'\]\[\forall \text{ odd } k, \ a_{\overrightarrow{k+1}} b\iff \exists b' \neq b, b_{\overleftarrow{k}} a_{\overrightarrow{k}} b' \]If we expand the above recurrence one step, we obtain the following: \[\forall \text{ even } k, \ a_{\overrightarrow{k+2}} b\iff \exists a_1\neq a, b_1\neq b\neq b_2, {b_1}_{\overleftarrow{k}}a_{\overrightarrow{k}} b _{\overleftarrow{k}} {a_1}_{\overrightarrow{k}}b_2\]similarly for the odd case, and so on if we keep expanding. Now there is no requirement for $b_1$ to be distinct from $b_2$ in the above expression to hold true. If $b_1 = b_2$, then the path can be extended in both direction arbitrarily, and the relation $a_{\overrightarrow{k}}b$ holds true for all k, so is $a'_{\overrightarrow{k}}b$ and $a_{\overrightarrow{k}}b'$. in other words, the logicians would never find out the original numbers after arbitrary many assertions of ignorance! We state this case slightly more formally by introducing another notation. We define a symmetric relation $a\leftrightarrow c$ to mean that there exists $b$ such that $a\rightarrow b \leftarrow c$. This symmetric relation defines an undirected graph $G$ on the natural numbers. Let us define a cycle on this undirected graph to mean a sequence $v_1\leftrightarrow v_2\leftrightarrow \cdots v_n \leftrightarrow v_1$ such that $v_i\neq v_{i+2}$ for all $i$ modulo $n$. The condition that "the input $a\rightarrow b$ is not resolvable within any finite amount of exchange between the logicians" is equivalent to the characterization that $a\leftrightarrow c$ is part of a cycle on $G$, for some $c$ satisfying $b\leftarrow c$. Hence we will concentrate on the relation $\leftrightarrow $ from this point. It surprisingly turns out that graph $G$ is sufficiently well connected and only finitely many of its vertices are not part of a cycle. Showing that almost all vertices of it is part of some cycle implies that every edge between some two of those vertices is also part of some cycle (by stitching together the two cycles by a bridge). Right now we use the famous sum of squares identity \[(ac+bd)^2+(ad - bc)^2 = (ac - bd)^2 + (ad + bc)^2\]The unrdered pairs $\{ac+bd, ad - bc\},\{ac - bd, ad + bc\}$ are distinct iff $a,b,c,d > 0, a/b > c/d > 1$ (WLOG). Hence for all such quadruples $(a,b,c,d)$ there exists an edge between the following two natural numbers \[a(c+d) + b(c-d) \leftrightarrow a(c+d) - b(c-d)\cdots (1)\]This also gives a complete description of the graph since the identity generates all solutions to the sum of squares diophantine equation (well known). See end of the solution to get a computer generated list-of-neighbors representation of the graph. It's easy to observe that odd numbers have only odd neighbors and even numbers have only even neighbors, and $x\leftrightarrow y\implies 2x \leftrightarrow 2y$. So It is sufficient to show that all but finitely many odd numbers are part of a cycle, and some power of 2 is part of a cycle. It's not hard to observe that $32\leftrightarrow 34 \leftrightarrow 38\leftrightarrow 32$ is a cycle. eg. $(a,b,c,d) = (3,1,6,5)\implies 32\leftrightarrow 34 $, similarly, we have $(4,2,10,8), (5,3,4,3)$ proving the other two edges. So it remains to prove that all but finitely many odd numbers are part of some cycle. If we plug in $c = d +1, b = 1$ in statement $(1)$, we observe that $a(2d+1)\pm 1$ is connected for all $a>1$ except the case $(a,d)=(2,1)$ (for which we have $a/b = c/d$, which is not allowed). Note that every even integer other than $6$ or powers of $2$, can be written as $a(2d+1)$ satisfying $a>1$ and $(a,d)\neq (2,1)$. Hence $2n-1\leftrightarrow 2n+1$ for all positive integers $n$ except for $n = 1, 2, 3, 4, 8, 16, \cdots $. We also have the fact that $2^n-1\leftrightarrow 2^n+5$ proven by the quadruplet $(2, 1, 2^{n-2}+2, 2^{n-2}-1)$ for all $n\ge 5$. Similarly $(2, 1, 2^{n-2}+1, 2^{n-2}-2)\implies 2^n+1\leftrightarrow 2^n-5$ for all $n\ge 5$. So we have just proven the existence of cycles \[2^n-1\leftrightarrow 2^n+5\leftrightarrow 2^n+3\leftrightarrow 2^n+1\leftrightarrow 2^n-5\leftrightarrow 2^n-3\leftrightarrow 2^n-1\]It is easy to stitch together the paths from $2^n+1$ to $2^{n+1}-1$ with these cycles to show that all odd numbers $\ge 33$ are part of cycles. There's another base cycle $19\leftrightarrow 21\leftrightarrow 23\leftrightarrow 19$ which proves that all odd numbers $\ge 19$ are in fact part of cycles. We know the same holds for even numbers $\ge 38$. We can manually check that it is in fact true for even numbers $\ge 22$. Coming back to the original problem, lets assume that the initial pair corresponds to $a\rightarrow b$. Since B cannot resolve $b$ on the first try, there exist $c$ such that $a\rightarrow b \leftarrow c$ or $a\leftrightarrow c$. If $a\leftrightarrow c$ is part of some cycle, none of them will ever be able to figure out the numbers. So one of $a,c$ has to be $\le 20$. We only have finitely many possibilities in this case. All edges consisting of one vertex $\le 20$ can be checked. In fact from the fact that $c_{\overrightarrow{6}}b$ and $c\not _{\overrightarrow{7}}b$, the edge $c\rightarrow b$ must be extendable in both direction by exactly $5$ edges, but not more. In the graph $G$, the path is contracted in length by half, and the edge $a\leftrightarrow c$ is extendable in both directions by exactly $2$ additional edges. \[15\leftrightarrow 13\leftrightarrow 17\leftrightarrow 19\leftrightarrow 21\leftrightarrow \cdots\]In this case $a = 17, b = 145, c = 19$. None of the other edges in $G$ satisfy this condition. The pair $17\rightarrow 145$ corresponds to the initial values $(8,9)$. b) It's true that B receives no new information from the first answer of A. However, if he didn't listen to A's answer, A wouldn't be able to tell whether B's second answer would have changed if he did listen to A (In this case it wouldn't, but A doesn't know that). The act of listening to A before answering second time gives A more information on his second answer, which wouldn't be the case if he didn't listen. ##################### ## It is only required to compute by hand upto 20 and ## a few other special cases to solve the problem ##################### 8 [10] 9 [11] 10 [] 11 [13] 12 [] 13 [15, 17] 14 [16, 18] 15 [] 16 [20] 17 [19] 18 [22, 24] 19 [21, 23, 25] 20 [22] ##################### ## All vertices (and edges) belong to cycles below this point ##################### 21 [23, 27] 22 [26, 28] 23 [25, 27, 29, 31] 24 [26, 30, 32] 25 [27, 29, 31] 26 [28, 30, 34] 27 [29, 33] 28 [32, 36, 38] 29 [31, 37, 39] 30 [34, 36] 31 [35, 37, 39, 41] 32 [34, 38, 40] 33 [35, 37, 39, 43, 45] 34 [36, 38, 44, 46] 35 [37, 41, 43, 45] 36 [42, 44, 48] 37 [39, 41, 43, 47] 38 [40, 42, 46, 50, 52] 39 [41, 45, 49, 51, 53] 40 [44, 48, 50]