7
$\begingroup$

An element of an integer sequence is called a local maximum if it is not smaller than all its neighbors. E.g., all local maximums of the following sequence are highlighted. enter image description here

Consider an integer sequence of length 16 whose elements we don't know.

enter image description here

Find (any) local maximum by revealing at most seven of them.

Try it here: https://bit.ly/localmaximum

Bonus question: how would you implement an adversary strategy such that it is not possible to solve the puzzle in less than seven steps?

$\endgroup$
  • 1
    $\begingroup$ Do you mean "at most seven", like in the link? Or can it really be done in five? $\endgroup$ – hexomino Aug 7 at 8:57
  • 1
    $\begingroup$ @hexomino, oh yes, right, thank you! I've just fixed this. $\endgroup$ – Alexander S. Kulikov Aug 7 at 9:04
  • 1
    $\begingroup$ I have added a comment about this puzzle to this sequence: oeis.org/A000071 $\endgroup$ – Dmitry Kamenetsky Aug 9 at 11:28
  • $\begingroup$ @DmitryKamenetsky, great, thank you! Perhaps, we should also cite a paper where a lower bound is proven. $\endgroup$ – Alexander S. Kulikov Aug 9 at 19:45
11
$\begingroup$

It is possible to solve up to $n=20$ cells using only $m=6$ moves.

I will use the notation $(a,b)$ for a row of $a$ unknown cells, and a row of $b$ unknown cells, with a single revealed cell between them, and for which it is known that one of the unknown cells must contain a maximum. Similarly, $(a,b,c)$ is three sections of unknown cells separated by single revealed cells, and known to contain a maximum.

For $20$ cells,:

Move 1: Reveal the 8th cell so you have the case $(7,12)$.
Move 2: Reveal the 13th cell, turning $(7,12)$ into $(7,4,7)$. The two blocks next to whichever cell is highest must contain a maximum. Therefore you now have the case $(7,4)$ or $(4,7)$. These are equivalent by symmetry, so I'll assume $(4,7)$.
Move 3: Reveal the 8th cell, turning $(4,7)$ into $(4,2,4)$. The two blocks next to whichever cell is highest must contain a maximum. Therefore you now have the case $(4,2)$ or $(2,4)$. These are equivalent by symmetry, so I'll assume $(2,4)$.
Move 4: Reveal the 5th cell, turning $(2,4)$ into $(2,1,2)$. The two blocks next to whichever cell is highest must contain a maximum. Therefore you now have the case $(2,1)$ or $(1,2)$. These are equivalent by symmetry, so I'll assume $(1,2)$.
Move 5: Reveal the 3rd cell, turning $(1,2)$ into $(1,0,1)$. The two blocks next to whichever cell is highest must contain a maximum. Therefore you now have the case $(1,0)$ or $(1,0)$. These are equivalent by symmetry, so I'll assume $(0,1)$.
Move 6: Reveal the 2nd cell, winning the game.

This strategy obviously generalises. The case $(F_n-1,F_{n+1}-1)$ takes $n-1$ more moves, where $F_n$ are the Fibonacci numbers (with $F_1=F_2=1$). So you can solve up to $(F_n-1)+1+(F_{n+1}-1)=F_{n+2}-1$ cells in $n$ moves.

In particular, it is not possible to answer the bonus question as stated.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Wow! If I remember correctly, a matching lower bound (perhaps up to an additive constant) is known. $\endgroup$ – Alexander S. Kulikov Aug 7 at 10:56
  • $\begingroup$ Very nice method $\endgroup$ – hexomino Aug 7 at 11:38
4
$\begingroup$

It can be achieved in $7$ reveals as follows

First let us index the boxes $1,2,\ldots,16$.
Now set the first two reveals as boxes $8$ and $9$ as highlighted in the diagram
enter image description here
If box $8 \geq$ box $9$ then there is a local maximum in the first half of the boxes, otherwise, there is a local maximum in the second half.
Without loss of generality, assume the former ($8 \geq 9$, the other case will follow by symmetry).
Next reveal the contents of box $4$ (see diagram).
enter image description here
If the contents of box $4$ are less than or equal to the contents of box $8$, then it is guaranteed that by revealing the contents of boxes $5,6,7$ we will find a local maximum (total $6$ reveals).

Instead suppose that box $4 >$ box $8$.
In this case, reveal the contents of box $2$.
enter image description here
If box $2 \geq$ box $4$ then it is guaranteed that by revealing boxes $1$ and $3$, we will find a local maximum (total $6$ reveals).

Instead, suppose that box $2 <$ box $4$.
In this case, reveal the contents of box $6$.
enter image description here
If box $6 \geq$ box $4$ then we are guaranteed to find a local maximum by revealing the contents of boxes $5$ and $7$. Otherwise, we'll find a local maximum by revealing the contents of boxes $3$ and $5$. Both constitute a total of $7$ reveals.

Bonus

If the adversary is allowed to set the values of the boxes upon revealing them, then the best way to frustrate the above strategy is by setting box $8 >$ box $9$, box $4 >$ box $8$, box $2 <$ box $4$ and box $6 >$ box $4$. Then, the next box of $5$ or $7$ to be selected must be $<$ box $6$ to force a final reveal.

The only thing I haven't shown is that the player strategy can't be bettered but, as it is essentially a modified form of a binary search, it doesn't seem like this should be possible.

| improve this answer | |
$\endgroup$
  • $\begingroup$ great! Yes, one still needs to show that no other strategy is able to find a local maximum in less than seven steps. $\endgroup$ – Alexander S. Kulikov Aug 7 at 9:45
3
$\begingroup$

I found a different answer:

Examine boxes 6 and 11. Assume without loss of generality box 11 $\ge$ box 6. Now examine box 12. If box 12 $\ge$ box 11 then examine boxes 13,14,15,16 and win. Otherwise examine boxes 7,8,9,10 and win.

I don't know the answer to the bonus question unfortunately. I'm assuming that

the "protagonist" is not allowed to get lucky by guessing e.g. boxes 6,7,8 and find box 7 is a local maximum, otherwise there is no way for an adversary to avoid the puzzle being solved in at most 3 moves with lucky guessing. In other words, the protagonist must maximise his chances of beating 7 moves without jeopardising a guaranteed win in at most 7 moves.

| improve this answer | |
$\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.