Саша и Ваня играют в игру. Первый прячет под одну из клеток доски 8×8 монетку. А второй разрезает доску на две части по горизонтали или вертикали, после чего первый сообщает, под какой из частей лежит монетка. За какое наименьшее число ходов второй может однозначно определить, где находится монетка?.

Как решить?
Доску резать надо ;-)
Если делить доску при каждом резе пополам, то с каждым разом непроверенных клеток будет оставаться вдвое меньше и так постепенно дойдём до ситуации, когда останется две клетки...
Вот, к примеру, так можно делить доску - синим цветом я обозначил линии разреза доски:
После первого, вертикального разреза "под подозрением" оказались 32 клетки левой стороны доски;
после второго, горизонтального в остатке 16 клеток нижней части;
после третьего, вертикального разреза оказалось, что монетка под одной из 8 клеток слева от разреза;
после четвёртого, горизонтального разреза Саша сообщил Ване, что монета под одной из четырёх клеток ниже этого разреза;
пятый, вертикальный разрез и Саша говорит, что монета уже под одной из двух монет слева;
Ваня делает шестой и последний, горизонтальный разрез и, наконец, Саша сообщает под нижней или верхней клеткой находится монета.
Если Саша не врёт ( где это видано, чтобы Саша врал ;-) , чтобы наверняка найти спрятанную им монету, Ване потребуется совершить как минимум 6 разрезов.
                                                                              

Задачка с олимпиады резко стала популярной. Конечно, однозначно можно определить местонахождение монетки только в случае, когда клетка остаётся всего одна. Во всех иных случаях это будет угадайка с риском проиграть.
Определим, как быстрее всего прийти к одной клетке - для этого используем тот же принцип, что и в играх "больше/меньше" при угадывании числа - всегда делим оставшийся промежуток пополам.
Площадь поля составляет 64 клетки, что является двойкой в шестой степени или же 2*2*2*2*2*2. Итого, деление последнего поля из двух клеток у нас будет шестым ходом, после которого Саша сам ткнёт пальцем где он спрятал монету

Похоже, что за 3 хода.
Первый ход-получаются 4 площадки 4х4,три из них отсеиваются.
Второй ход-получаются 4 площадки 2х2,три из них отсеиваются
Третий ход-площадка 2х2 режется на 4 квадратика
1х1.И первый сообщает под каким квадратиком монетка.

Если всё время делить доску наполовину, то получится, что за шесть ходов можно точно определить, под какой клеткой находится монетка. Первое деление даёт две части по 32 клетки, второе - две части по 16, третье - по 8 клеток, четвертое - по 4, пятое - по 2 клетки, шестое деление - 2 части по 1 клетке. Всё, приехали.

Смешно...Наименьшее число ходов - это Один ход...меньше быть просто не может быть.