Задача 4.
На праздник к князю съехались дворяне (которые всегда говорят правду) и купцы (которые всегда лгут). Князь расселил гостей в дом, имеющий форму квадрата 3 × 3 комнаты. Каждого из гостей спросили, кто его соседи, и каждый сказал: «Среди моих соседей через стенку больше дворян, чем купцов».
Все гости знают всю правду про своих соседей. Сколько купцов могло приехать на праздник? Запишите все варианты.
Ответ на Задачу 4.
Ответ: 0, 3 или 9 купцов.
Решение:
У каждой угловой комнаты — 2 соседних через стену. Если хотя бы в одной из этих комнат живёт купец, говоря «Среди моих соседей через стенку больше дворян, чем купцов», житель угловой комнаты лжёт (так как либо купцов больше, либо купцов столько же, сколько дворян). То есть дворянин живёт в угловой комнате только если оба его соседа тоже дворяне.
Получается, что если купец оказался в неугловой комнате на какой-то стороне квадрата, то во всех трёх комнатах вдоль этой стороны тоже должны жить купцы. Всего есть 4 неугловых комнаты — соседние с центральной.
1. Если во всех 4 комнатах, соседних с центральной, живут дворяне, то в центральной клетке тоже живёт дворянин и в угловых клетках тоже живут дворяне. В этом случае 0 купцов.
2. Если в одной из комнат, соседних с центральной, живёт купец, а во всех остальных — дворяне, то в центре тоже живёт дворянин. Тогда во всех комнатах на стороне купца тоже живут купцы, а во всех остальных — дворяне. Получается 3 купца.
3. В остальных случаях в центральной комнате живёт купец. У него есть не меньше 2 соседей-купцов. Эти 2 купца-соседа центрального купца могут жить либо на противоположных сторонах квадрата, либо на соседних. В первом случае:
обе эти стороны заняты купцами, тогда оставшиеся 2 комнаты, соседние с центральной, тоже заняты купцами, потому что у них 3 соседа — купцы. Получается 9 купцов.
Если 2 купца-соседа центрально живут на соседних сторонах, эти стороны полностью заселены купцами:
У жильцов комнат, отмеченных * уже есть 2 соседа-купца, значит, в * тоже живут купцы. Получается, что в угловой комнате живёт купец. Получается 9 купцов.
