Find Local Maximum in an Integer Sequence

Question

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 bolded.

3, * 4 *, 2, 1, * 3 *, 2, * 8 *, * 8 *, 1, * 4 *

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

?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?, ?

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?

Answer 1

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.

Answer 2

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

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).

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$.

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$.

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.

Answer 3

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.