рыцари и города

[пачти умный]

1. На острове рыцарей (они говорят только правду) и лжецов (они всегда
врут) состоялся шахматный фестиваль. 64 любителя шахмат встали по одному
на клетки большой шахматной доски. После этого каждый сказал:
``среди людей, стоящих со мной на одной горизонтали больше лжецов, чем
среди людей, стоящих со мной на одной вертикали''.
Докажите, что количество рыцарей на доске делится на 8.

2. В государстве 50 городов, из каждого города выходит четыре дороги
(любая дорога соединяет два города, между любыми двумя городами
проложено не более одной дороги, все дороги имеют разную длину,
измеряемую не обязательно целым числом километров). Суммарная длина
всех дорог равна 25\,000 км. Из каждого города выехала машина в самый
близкий город. В сумме машины проехали 5000 км. Докажите, что
длина одной из дорог не менее 300 км.

[Sirion]

1. Здесь и далее фраза "не нарушая общности" будет означать, что мы можем так перетасовать вертикали и горизонтали, чтобы нужные нам линии имели нужные обозначения.

Пусть на некоторой вертикали (не нарушая общности - на вертикали А) находится 0<k<8 рыцарей (не нарушая общности - на полях с А1 по Аk). Рассмотрим лжеца на поле А8. Поскольку он утверждает, что на его горизонтали больше лжецов, чем на его вертикали, на самом деле это не так. Следовательно, на восьмой горизонтали как минимум k рыцарей (не нарушая общности - на полях с B8 по чётотам-8). Рассмотрим пересечения их вертикалей с первой горизонталью. Если бы на всех этих пересечениях стояли рыцари, то на первой вертикали оказалось бы минимум k+1 рыцарей, и рыцарь на А1 солгал бы. Значит, на каком-то из них (не нарушая общности - на В1) стоит лжец. При этом на вертикали В , согласно утверждению рыцаря с В8, более k рыцарей. Значит, следуя утверждению лжеца с B1, на горизонтали 1 также более k рыцарей. Получается, рыцарь с А1 лжёт. Противоречие.

Парадокс разрешим лишь в том случае, когда на каждой вертикали стоят либо 8 рыцарей, либо 8 лжецов. Из этого, в частности, следует доказываемое утверждение.

[Sirion]

2. Для удобства сделаем так: будем считать дорогу из А в В и дорогу из В в А различными, но имеющими одинаковую длину. Что мы получим? А вот что: есть 200 дорог, суммарная длина которых - 50000 км. 50 из них имеют суммарную длину 5000 км. Следовательно, оставшиеся 150 имеют суммарную длину 45000 км, а их средняя длина, соответственно, 300 км. Отсюда всё следует.

Кошерные задачки. Хочу ещё.

[iPhonograph]

1. Можно чуть проще.
Обозначим через К количество рыцарей на горизонтали или вертикали.
Докажем, что количество рыцарей одинаково на всех горизонталях.
От противного: пусть К₁<К₂
Тогда найдётся вертикаль (пусть А), на которой стоят рыцарь А2 и лжец А1, из высказываний которых соответственно получим К₂<К_А и К_А<=К₁, что противоречит предположению К₁<К₂