# 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 highlighted. 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 at 8:57
• @hexomino, oh yes, right, thank you! I've just fixed this. – Alexander S. Kulikov Aug 7 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 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 at 10:56
• Very nice method – hexomino Aug 7 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 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.