s11.4
11.4. На клетчатой плоскости расставили несколько ладей. Докажите, что ладей можно раскрасить в 3 цвета таким образом, чтобы ладьи одного цвета не били друг друга. Две ладьи бьют друг друга, если они стоят в одном ряду и между ними нет других ладей.
Решение.
Давайте их пронумеруем. 1 ладья. Мы номером сверху вниз. 2, возможно в той же строчки 3 тоже 4 там где то новое 5, 6 и так далее. Миллион 1 вроде в чем проблема её покрасить, берёшь и красишь. Красим в красный, хорошо берем 2 день. Если она стоит той же строчки? Значит, и ей нельзя скрасить красным возьмём другой свет. Синий. Если в новой строке стоит, тот ничего нет. Что там по другому? Давайте возьмём какую то логика. Которую я хочу покрасить. Где могут покрасить, где могут располагаться уже покрашенного, день которых она бьет. Слева. И сверху. То есть есть всего не более 2 цветов. Которые запрещены, значит, клетку co мы красим свет. Отличный от тебя. Берем цвет, отличный вот IB красим. Почему все получилось? Потому что если потом вдруг окажется, что есть 2 ладьи, которые бьют друг друга. То одна из них была поставлена раньше, другая позже покрашена. Давайте посмотрим на ту, которая была покрашена позже. Когда мы красили, мы знали, что существование музей н и значит, мы избавились от Того, что есть делать одного цвета, значит нет таких. Нет такой пары ладей. Вот и вся задача.
То же самое, повтор, по другому записано.
Пронумеруем: 1 ладья, 2 может в тойже строке, 3 может в той же строке.
Берем первую и красим, например в красный.
Берем вторую ладью, если она стоит в той же строчке, то ее нельзя красить красным.
Берем другой цвет – синий.
Если она стоит в новой строке и там ничего - то нужно по- другому.
Давайте возьмем какую-нибудь ладью К, которую я хочу покрасить в очередной раз.
Где могут располагаться уже покрашенные ладьи, которых она бьет: слева и сверху.
То есть, есть всего не более двух цветов, которые запрещены.
Значит клетку К мы красим в цвет, отличный от А и Б.
Почему Все получилось?
Потому что если потом окажется, что есть две ладьи, которые бьют друг друга – M и N, то одна из них была покрашена раньше, а другая позже.
Давайте посмотри на ту, которая была покрашена позже.
Мы же когда красили, то мы знали о существовании ладьи N.
И значит мы избавились от того, что есть две ладьи одного цвета.
Значит нет такой пары ладей.