1
$\begingroup$

Problem Statement. There are many interesting variations on the Tower of Hanoi problem. This version consists of $N$ pegs and one ball containing each number from $1, 2, 3, \dots$ Whenever the sum of the numbers on two balls is not a perfect square (i.e., $c^2$ for some integer $c$), they will repel each other with such force that they can never touch each other.enter image description here

The player must place balls on the pegs one by one, in order of increasing ball number (i.e., first ball $1$, then ball $2$, ball $3$ $\dots$). The game ends where there is no non-repelling move. The goal is to place as many balls on the pegs as possible. The figure above gives a best possible result for $N = 4$ pegs. One may assume $N \le 50$ in all test cases.

Source: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1217.

I originally encountered this problem in the book "Programming Challenges" from Skiena and Revilla where it is part of Chapter 9: "Graph Traversal" given a short hint:

Can the constraints be usefully modeled using a DAG?

Question 1. How to use this hint?

Last but not least, I observed the solution seems to be always

$\displaystyle \left\lfloor \frac{(N + 1)^2}{2} \right\rfloor - 1$

which is the reason I ask this question.

Question 2. How to prove this formula or at least some upper bound on the number of balls depending on $N$?

I appreciate any kind of help in getting more out of this problem. Thanks!

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jan 6 '18 at 19:12
  • $\begingroup$ As for the hint, I think they're aiming at the fact that the relation '$a+b$ is a perfect square and $a>b$' on the numbers $1,2,\ldots,k$ leads to a DAG. As for the summation, you could for instance try checking whether you can sometimes choose multiple balls to stack on and whether it is optimal to stack on a ball when you can. $\endgroup$ – Discrete lizard Jan 17 '18 at 17:52
  • $\begingroup$ Thanks, I updated the problem link. Yes, the goal is to determine the maximum number of balls for a given value of $N$. I already thought of the mentioned DAG. It may be the case that some vertices have out-degree > 1, i.e. it's not clear how to split the vertices in optimal stacks. $\endgroup$ – neutron-byte Jan 18 '18 at 15:58

Your Answer

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

Browse other questions tagged or ask your own question.