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?

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

1 Answer 1

Reset to default
19
$\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.

Improve this answer
$\endgroup$
1
  • 1
    $\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
    Commented Feb 6, 2015 at 4:30

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