# Find Local Maximum in an Integer Sequence

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?

• Do you mean "at most seven", like in the link? Or can it really be done in five? – hexomino Aug 7 '20 at 8:57
• @hexomino, oh yes, right, thank you! I've just fixed this. – Alexander S. Kulikov Aug 7 '20 at 9:04
• @DmitryKamenetsky, great, thank you! Perhaps, we should also cite a paper where a lower bound is proven. – Alexander S. Kulikov Aug 9 '20 at 19:45

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.

• Wow! If I remember correctly, a matching lower bound (perhaps up to an additive constant) is known. – Alexander S. Kulikov Aug 7 '20 at 10:56
• Very nice method – hexomino Aug 7 '20 at 11:38

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.

• great! Yes, one still needs to show that no other strategy is able to find a local maximum in less than seven steps. – Alexander S. Kulikov Aug 7 '20 at 9:45

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.