11
$\begingroup$

Yesterday I met the perfect logicians Divvy and Subtra. I told them:

I have chosen two positive integers $x$ and $y$ with $2\le x\lt y\le 100$ and with $x$ a divisor of $y$. I will now whisper the ratio $r=y/x$ into the ear of Divvy and I will whisper the difference $d=y-x$ into the ear of Subtra.

And then I whispered the ratio and the difference into their ears.

Then the following conversation took place:

  • Divvy: I don't know the numbers.
  • Subtra confirmed: I already knew this.
  • Divvy: I already knew that you knew that I don't.
  • Subtra: I still can't determine the numbers.
  • Divvy: At the very beginning of this conversation, I knew that you did not know the numbers. I forgot to mention this. Does this information change something for you?
  • Subtra: Yes, it changes everything! Finally I am able to determine the numbers!

Question: What on earth are these magic numbers $x$ and $y$?

$\endgroup$
  • 6
    $\begingroup$ Congratulations! It took many rounds of improvement, but now your text has converged to a nice puzzle with a unique solution. $\endgroup$ – Gamow Mar 5 '15 at 10:57
10
$\begingroup$

We are dealing with four integers $x$, $y$, $r$ and $d$ that satisfy $y=rx$ and $d=(r-1)x$. Note that $x<y$ implies $r\ge2$ and $d\ge2$.

(1) Divvy: I don't know the numbers.

  • If $r\ge34$, then $x\ge3$ is impossible (as this would imply $y=rx\ge3\cdot34=102$). Hence this would imply $x=2$ and $y=2r$, so that Divvy knows $x$ and $y$ in contradiction to his statement.
  • If $r\le33$, then $x=2$ and $y=2r$ as well as $x=3$ and $y=3r$ are feasible solutions. Divvy is not able to determine $x$ and $y$.

Divvy's first statement is equivalent to $2\le r\le33$.

(2) Subtra confirmed: I already knew this.

As Subtra's difference is $d=(r-1)x$, her statement means that $d$ cannot be written as the product of two factors $r-1$ and $x$, one of which is $\ge33$ and one of which is $\ge2$.

Subtra's statement means that the difference $d$ is either from the range $0\le d\le65$, or that $d$ is odd and from the range $67\le d\le97$. Equivalently, $d\notin\{66,68,70,\ldots,98\}$.

(3) Divvy: I already knew that you knew that I don't.

Divvy's statement means that there does not exist any integer $x$ with $2\le x\le100/r$, so that the corresponding difference $(r-1)x$ is an even integer in the so-called bad range $B=\{66,68,\ldots,98\}$. We make some case distinctions on $2\le r\le33$.

  • If $r$ is odd, then $r-1$ is an even integer from the range $2,4,\ldots,32$. As the diameter of the bad range $B$ is $98-66=32\ge r-1$, the bad range contains an (even!) integer multiple $(r-1)x$ of $r-1$. Hence all such values $r$ collide with Divvy's statement.
  • If $r=2$, then for any $x$ with $2\le x\le 100/r=50$, the corresponding product $(r-1)x=x\le50$ will not fall into the bad range. This case is possible.
  • If $r$ is even with $4\le r\le24$, then $2(r-1)$ is an even integer from the range $6,10,14\ldots,46$. The values $6,10,\ldots,30$ are smaller than the diameter of the bad range, and hence have an integer multiple in $B$. The value $34,38,42,46$ respectively have the multiples $68,76,84,92$ in $B$. For a multiple of the form $2(r-1)k$ in $B$, we may choose $x=2k$. Hence all such values $r$ collide with Divvy's statement.
  • If $r\in\{26,28,30,32\}$, then none of the multiples of $r-1\in\{25,27,29,31\}$ fall into $B$. Hence these four cases are possible.

Summarizing, we see that Divvy's second statement is equivalent to $r\in\{2,26,28,30,32\}$.

(4) Subtra: I still can't determine the numbers.

At this point of the conversation, we are left with the following options for the pairs $(x,y)$:

  • $r=2$: The pairs $(x,2x)$, where $x\in\{2,3,\ldots,50\}$. Then $d=x$.
  • $r=26$: The pairs $(2,52)$ and $(3,78)$. Then $d=50$ or $d=75$.
  • $r=28$: The pairs $(2,56)$ and $(3,84)$. Then $d=54$ or $d=81$.
  • $r=30$: The pairs $(2,60)$ and $(3,90)$. Then $d=58$ or $d=87$.
  • $r=32$: The pairs $(2,64)$ and $(3,96)$. Then $d=62$ or $d=93$.

Since Subtra is not able to determine the numbers $x$ and $y$ from this, her value $d$ must be compatible with two distinct pairs $(x,y)$ in this enumeration. This reduces the possible options for $(x,y)$ to the following short list:

  • $r=2$ and $d=50$: The pair $(50,100)$.
  • $r=26$ and $d=50$: The pair $(2,52)$.

Subtra's second statement means that $d=50$.

(5) Divvy: At the very beginning of this conversation, I already knew that you did not know the numbers.

We are only left with two possible values $r=2$ and $r=26$ for the ratio.

  • If $r=2$, then at the very beginning of the conversation the pair $(x,y)=(2,4)$ with difference $d=2$ would have been a feasible option for Divvy. But then Subtra would have been able to deduce the two numbers right away, as $d=(r-1)x=2$ and $x\ge2$; a contradiction.
  • If $r=26$, then at the very beginning of the conversation only the two pairs $(x,y)=(2,52)$ with $d=50$ and $(x,y)=(3,78)$ with $d=75$ would have been feasible options for Divvy. The first difference $d=50=(r-1)x$ is compatible with $(r,x)=(26,2)$, as well as with $(r,x)=(6,10)$. The second difference $d=75=(r-1)x$ is compatible with $(r,x)=(26,3)$, as well as with $(r,x)=(6,15)$. In either case, at the very beginning of the conversation Subtra is not able to deduce the numbers from the difference $d$.

Divvy's third statement implies $r=26$.

(6) Subtra: But now I can determine the numbers.

Subtra now knows that $d=50$ and $r=26$, and deduces the numbers.

Answer: The magic numbers are $x=2$ and $y=52$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.