Коля и Надя играют в игру «крестики-крестики». Доска имеет форму полоски длиной 17 клеток и шириной одну клетку. Они по очереди ставят на доску крестики, и выигрывает тот, после чьего хода на доске образуется ряд из 8 крестиков подряд. Какое наибольшее число крестиков можно поставить на доску таким образом, чтобы такого ряда не образовалось?

Очевидно, что 17 крестиков поставить на доску с такими условиями невозможно.

16 крестиков поставить на доску также невозможно. Если предположить, что такое случилось, то единственная пустая клетка разобьет доску на два ряда крестиков. Но по условию ряда из 8 крестиков быть не должно, значит длина каждого из двух рядов не более 7, а значит общее число крестиков не более 14. Но мы предполагали, что расставляем на доску 16 крестиков. Противоречие.

Для 15 крестиков можно показать требуемую расстановку:

XX XX XX XO XX XX XX XO X, где X - крестик, O - пустая клетка

Ответ: 15