Question

На смотре войска острова лжецов и рыцарей вождь построил всех воинов в шеренгу. каждый из воинов, стоящих в шеренге, сказал: " мои соседи по шеренге лжецы". воины стоящие в конце шеренги сказали: "мой сосед по шеренге-лжец". какое наибольшее число рыцарей могло оказаться в шеренге, если на смотр вышли 2005 воинов?

Answer 1

Заметим, что два воина, стоящие рядом, не могли оказаться рыцарями. Действительно, если бы они оба были рыцарями, то они оба сказали бы неправду. Выберем воина, стоящего слева, и разобьем ряд из оставшихся 2004 воинов на 1002 группы по два рядом стоящих воина. В каждой такой группе не более одного рыцаря, т. е. среди рассматриваемых 2004 воинов не более 1002 рыцарей, т. е. всего в шеренге не более 1002 + 1 = 1003 рыцарей. Рассмотрим шеренгу РЛРЛР...РЛРЛР. В такой шеренге стоит ровно 1003 рыцаря