2000 Olympiad in Informatics Question on Box

Question

I have an old Olympiad question on informatics.

There are 31 boxes. In each box there is one number. We know the number if and only if we open the box. We want to calculate the minimum number of boxes that must be opened to find one number that is not lower than the numbers of its neighbor boxes. The first and last boxes have one neighbor (boxes are not a ring). All other boxes have two neighbors.

I see a strange answer and it is 11. Any details or ideas are very appreciated.

Answer 1

If I understand right the problem (it's not very clear), I think it can be done with less than 11.

Hint/sketch:

Lets say that a box is apt if its value is greater or equal than that of its neighbours. We want to find an apt box. This is analogous to finding a local maximum of a discrete sequence

Starting from the chain $(x_{1} \cdots x_{31})$, uncover $x_{16}$ and $x_{17}$. Assume (worst case) $x_{16} \ge x_{17}$ Then we restrict our chain to $(x_{1} \cdots \overline{x_{16}})$, as it must contain one apt box. (the overlined elements correspond to the known ones). Then uncover $x_{8},x_{9}$ If $x_8 \ge x_9$ we retain $(x_{1} \cdots \overline{x_{8}})$, else we retain $( \overline{x_{9}} \cdots \overline{x_{16}})$. Etc.

Answer 2

I think we can solve the problem for 32 boxes with 9 openings: Let the boxes be numbered 1, 2, ..., 32. Let the values in the boxes be $a_1, a_2, \dots, a_{32}$.

Preliminary observations:

(1) We are looking for a box whose value is a local maximum (i.e., whose value is greater than or equal to each of its immediate neighbors' value). We understand that a local maximum may also occur at an end box if that end box's value is greater than or equal to its one neighbor.

(2) At least one local maximum must occur among the $32$ boxes. (For instance the box with the absolute maximum value will also contain a local maximum.)

Steps: (1) Open boxes 16 and 17. If $a_{16}\ge a_{17}$ we will confine our remaining search to boxes 1 through 16. If $a_{16}<a_{17}$ we will confine our remaining search to boxes 1 through 8. Let's say, without loss of generality that $a_{16}\ge a_{17}$. Note that we may now restrict ourselves to boxes 1 to 16, with box 16 only needing to have a value greater than that of box 15 (since we already looked in box 17). Thus we have an analogous problem but with the row of boxes 1 to 16.

(2) Open boxes 8 and 9. The same sort of thing happens as in step 1. Let's say $a_8\ge a_9$. Now we will confine our remaining search to boxes 1 through 8.

(3) Open boxes 4 and 5. And again you can halve the number of boxes under consideration. Again let's assume that $a_4\ge a_5$.

(4) Open boxes 2 and 3. If say $a_2\ge a_3$, we can now know there will be a local maximum in box 1 or 2.

(5) Open box 1 to find out.

Answer 3

Start by opening boxes 1, 8, 16, 23, 31. Now try showing that it is possible to restrict your search to one of the intervals [1, 16], [16, 31] - This will involve checking some simple cases.

So say we are in [1, 16] and we know the content of box 8. With this information, we can even narrow down to one of the subintervals [1, 8], [8, 16] unless $B(1) < B(8)$ and $B(8) > B(16)$ in which case, like above, we look at 5, 12 and restrict ourselves to say [1, 8] with the content of box 5 known. Assume again that $B(1) < B(5)$ and $B(5) > B(8)$. Now look at box 4. If $B(4) > B(5)$, we look in [1, 4] otherwise in [5, 8]. Now we can open all (two) boxes and win.

This took only 10 views so it is good enough.