Question

В шеренгу выстроены 1000 военных. На каждом из них - фуражка или бескозырка. При этом если на ком-то фуражка, то любой военный, стоящий через девять человек от него, обязательно в бескозырке. (Например, если 28-й военный в фуражке, то и 18-й, и 38-й в бескозырках.) Докажите, что в фуражках не более 500 военных.

Answer 1

каждый 10-й в фуражке

1000/10=100 чел. - максимум в фуражках.

Answer 2

Давайте докажем утверждение методом математической индукции.

Предположим, что в первых 9 человеках всех возможных шеренг фуражках не более 5 военных (так как всего 9 позиций).

Шаг индукции: Теперь предположим, что в шеренге из 1000 военных, на первых 1000 - 9 = 991 позициях утверждение верно, то есть фуражках не более 5 военных.

Рассмотрим 1001-го военного. Он стоит на позиции, которая находится на 10-ой позиции после первых 991 военного. Так как на каждом из этих 991 военных либо фуражка, либо бескозырка, а 10-ый военный, по условию, находится в бескозырке, то на этой 1001-ой позиции не может быть фуражки.

Таким образом, мы доказали, что если утверждение верно для первых 1000 военных, то оно верно и для следующего военного.

По базе индукции: утверждение верно для первых 9 военных (по условию), и, следовательно, верно для 10-го военного, и, таким образом, верно и для 11-го, и так далее.

Теперь мы можем заключить, что утверждение верно для всех 1000 военных, исходя из базы индукции и шага индукции.

Следовательно, в фуражках не более 500 военных (поскольку 1000 - 500 = 500, и в условии говорится о максимуме 500 фуражек).