14
$\begingroup$

Cosmo plays the following (single-player) game with three wooden sticks:

  • He first checks whether he can form a triangle from the three sticks (which means: whether the longest stick is at most as long as the combined length of the two shorter sticks).
  • If Cosmo can form such a triangle: Cosmo has won the game.
  • If Cosmo cannot form such a triangle: Cosmo takes the longest stick, cuts off from it a piece as long as the combined length of the two shorter sticks, throws away this piece, and keeps the remaining shortened stick.
  • Then Cosmo repeats these steps with the two shorter sticks and the shortened stick.

Will Cosmo always win the game after a finite number of steps? For any choice of wooden sticks to start with?

$\endgroup$
  • $\begingroup$ So a winning state is a + b >= c, rather than a + b > c? $\endgroup$ – dmg Feb 5 '15 at 9:48
  • $\begingroup$ @dmg: Yes, such degenerate triangles are winning states. $\endgroup$ – Gamow Feb 5 '15 at 9:49
18
$\begingroup$

Spoiler:

No.

Let's choose a set of sticks to prove this:

Consider sticks of length $1, a, a^2$ - each stick is a times bigger than the previous one. Then the next step we will have sticks of length $a^2 - a - 1, 1, a$. If we choose a such that $a^2 - a - 1 = \frac{1}{a}$, then the sticks will retain the same ratios at each step, and we will never terminate. The required a is a root of $a^3 - a^2 - a - 1 = 0$. This turns out to have exactly one root at a = 1.8393, and we can check that $a^2 = 3.383 > a + 1$, so we don't terminate at step 1.

$\endgroup$
  • $\begingroup$ It's notable that this solution relies only on the idea of finding a tuple which, under Cosmo's process, iterates to a multiple of itself - and this can yield other more complex examples. It happens that the solution to the system: $$b-2a-2=k$$ $$1=ka$$ $$a=kb$$ has that $1,\,a,\,b$ will, after two steps, iterate to $k$ times itself and hence never be solved. (Also, it appears that such solutions are not stable; numbers near your desired $a$ do not iterate forever - I would venture to conjecture that your $a$ is, in fact, the only one such that $1,a,a^2$ will never let Cosmo win) $\endgroup$ – Milo Brandt Feb 6 '15 at 4:30

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.