10
$\begingroup$

Suppose you have a triangle that extends infinitely downwards, with circles inside, arranged in this arrangement:

     ^
    / \
   / O \
  / O O \
 / O O O \
/ O O O O \
... ... ...

how many rows can you take out from the top, while still allowing one of the circles to make it to the top by jumping over other circles, peg solitaire style (there are six directions that you can jump)? make sure to show why you can’t go further.

example jumps:

  /        / 0
 / 0 ->   /
/ 0      /

/ 0 0   \-> /     0 \
$\endgroup$
8
$\begingroup$

Here is another partial answer - an explicit solution for $5$ empty rows. I haven't yet proved whether $6$ rows is possible or not, but an attempt follows further down.

I'll number the rows from 1 to 10 (I don't need the pegs on lower rows). Horizontally the holes in each row are lettered from a to h.
enter image description here
a7-a5, b7-b5
enter image description here
c6-a4, a5-a3
enter image description here
f7-d5, g7-e5-c5, c8-c6-c4
enter image description here
d7-d5-b3, f8-d6, f9-d7-d5, h9-f7
enter image description here
g10-g8-e6-c4-a2, a3-a1
enter image description here

Here is a proof that with $7$ empty rows it is impossible to reach the top, and that $6$ will be very difficult.

I will use a resource count, just like @Riley has done in his answer.

Let $r = \frac{\sqrt5-1}{2} = \phi^{-1}$. It satisfies $r^2+r=1$.
The top hole is given a value of $r^0=1$, both holes in the second row have value $r^1=r$, and so on, with the holes in the $n$th row each given value $r^{n-1}$.

To calculate the resource count, add together the values of all the holes that contain a peg, and ignore the empty holes. It is easy to see that any move up the board keeps the value of the resource count the same, but any horizontal or downwards move reduces it. The resources will therefore never increase during play.

   n  Row           Triangle      Start Pos
   1  1             1             5.854101966
   2  1.236067977   2.236067977   4.618033989
   3  1.145898034   3.381966011   3.472135955
   4  0.944271910   4.326237921   2.527864045
   5  0.729490169   5.055728090   1.798373876
   6  0.541019662   5.596747752   1.257354214
   7  0.390096630   5.986844383   0.867257584
   8  0.275534830   6.262379212   0.591722754
   9  0.191576126   6.453955339   0.400146627
   10 0.131556175   6.585511514   0.268590453
   11 0.089436806   6.674948320   0.179153646
   12 0.060299985   6.735248305   0.118853661
  ...                ...
  inf               6.854101966

The column marked Row is the resource value of the $n$th row, which is $nr^{n-1}$. The column marked Triangle is the resource value of the triangle formed by the top $n$ rows. This converges to $(1-r)^{-2}$, the value of the full board. The last column is the resource value of the starting position with the top $n$ rows empty, which is the full board value minus the triangle value.

The final position, with one peg in the top hole, has a resource value of (at least) $1$. Clearly you must start with resources of at least $1$ to reach that, so you cannot have more than $6$ empty rows at the start.

This does not yet rule out $6$ empty rows. Consider however the position just before the last move. This is the position shown by the orange pegs below (or its mirror image):

enter image description here

The pegs on the right hand side edge of the board (marked in blue) do not contribute any resources towards putting the orange pegs in place. The only way to bring them into play would be a horizontal move to the left, and that uses up another peg of the same value (or a downwards move which is worse). The two orange pegs must therefore reach their positions using only the resource value of the pegs marked in yellow.

This unfortunately does not quite rule out an $n=6$ solution, but it is an extremely tight bound. If we act as if everything is shifted one step up and right, then the orange pegs have value $1+r = 1.618034$ whereas the yellow pegs have value $1.798374$, so you only have $0.180340$ of resources to spare. Rows $12$ to infinity together add up to almost that much ($0.1791536$), so you would have to use up almost every peg from rows $6$ to $11$ to achieve this (or rows $7$ to $12$ if we add the right hand side column back on), which seems almost impossible.

$\endgroup$
3
$\begingroup$

Partial Answer

The trick that usually solves this type of challenging problems is finding an invariant.

First, let us say $(i,j)$ represents the $j$th space in the $i$th row. We say the $i$th row is the one with $i-1$ spots.

We should label each cell with a number. For any given position, we can sum the values of each circle. We want to create the labels in such a way that no move can cause the sum to increase. Let's say $$f(i, j)=x^{i}$$

for some constant $x$. Right now I'm only thinking of preserving equality on vertical movement. Horizontal movement will clearly only decrease the sum for any positive $x$. To preserve equality on vertical movement, we need to satisfy $x^2+x=1$ so we find $x=\frac{-1+\sqrt 5}{2}$. Let $A$ be the sum of $f(i,j)$ for all spaces $(i,j)$. Then we have

\begin{align*} A&=1\left(\sum_{i=0}^\infty x^i\right)+x\left(\sum_{i=0}^\infty x^i\right)+x^2\left(\sum_{i=0}^\infty x^i\right)+\dots\\ &=\left(\sum_{i=0}^\infty x^i\right)^2\\ &=\frac{1}{(1-x)^2} \end{align*}

Now, let's sum after the $n$th row. We'll call this $B_n$. We have

\begin{align*} B_n&=nx^n\left(\sum_{i=0}^\infty x^i\right)+x^nA\\ &=\frac{n(1-x)x^n+x^n}{(1-x)^2} \end{align*}

We want to know the first time $B_n\le 1$, and we can calculate that this is $n=7$. So it is unsolvable if we remove $7$ or more rows. So the final answer is no more than $6$ rows. This is only an upper bound for the final answer because I haven't shown that it is possible if we remove $6$ rows.

$\endgroup$
  • 2
    $\begingroup$ That isn't a "final answer", because you haven't shown that you can do it with 6 rows. (I have been trying to do that for the last little while, so far without finding a solution, though very likely there is one.) $\endgroup$ – Gareth McCaughan Aug 28 '18 at 0:55
  • 1
    $\begingroup$ @GarethMcCaughan Sorry if it wasn't clear, this is only a partial answer. I've only found an upper bound for the solution. $\endgroup$ – Riley Aug 28 '18 at 0:56

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.