Замечательная задача от П. Е. Пушкаря и К. Л. Шейнерман

СергейП

Equinoxe писал(а):Source of the post Ну, это в принципе тоже перебор, но элементарный перебор. Будем смотреть, сколько занято клеток в центральном 2х2:
0. Тогда раскраска единственна и неверна
1. Тогда пары клеток сверху и снизу будут давать 1+2. Однако тогда неизбежно одному из 3х3 не хватит.
2. Тогда пары клеток -//- будут давать 0+2 или 1+1. Однако в обоих случаях одному 3х3 не хватит
3. Тогда пары клеток -//- будут 0+1, но в любом случае одному 3х3 не хватит.

P.S. чтобы увидеть элементарность сказанного, достаточно нарисовать рисунок (некий крестик такой). Я сначала на время доказывала (когда увидела ход мысли)
P.P.S. ура! у меня 239 сообщений — любимое число ^_^

Я то как раз этот полный перебор и делал. Вариантов там совсем не мало, дерево приличное вышло. Кстати, 3Х3 хватало везде, там 2Х4 не получалось.
А если начинать с 2Х4 то ветвей еще больше будет.
Да, варианты не сложные, но количество приличное.

А вот, решение без полного перебора.
На доске 4Х4 квадрат 3Х3 можно разместить 4-мя способами, а прямоугольник 2Х4 (4Х2) 6-ю.
Покрашенные клетки обозначим 1-ой, а не покрашенные 0. Сумма единичек по всем квадратам должна равняться 4*5=20, а по прямоугольникам 6*4=24. При этом 1-ка в центре будет входить в 4 квадрата и 4 пр-ка, т.е. ее надо учитывать 4 раза.
Тогда припишем каждой клетке 2 числа - красное (квадраты 3Х3) и синее (пр-ки).
Угловые клетки входят в один квадрат, бортовые - в 2, а центральные - в 4, поэтому в углах красные 1, по бортам - 2, а в центре 4. Синие цифры такие - углы - 2, борта - 3, центр - 4.
Теперь надо выбрать 8 клеток, поставить в них 1-ки так, чтобы сумма красных чмсел в них равнялась 20, а синих - 24.
1) В центре 0, надо все 8 разместить по бортам (только так будет 24 синяя), но красная сумма 16.
2) В центре 1 клетка занята, надо набрать 20 синее 7-ю клетками, это 1 в угол и 6 на борта, считаем красное 1+6*2+4=17
3) В центре 2 клетки занято, 24-2*4=16, из 6 оставшихся клеток 2 в углу и 4 на бортах, синее идет, а красное нет
4) В центре 3 клетки занято, 24-3*4=12, 3 в углах и 2 на борту, 3+2*2+3*4=19
5) Наконец все 4 в центре заняты, тогда и во все 4 по углам также по 1-ке, идут и синяя и красная суммы

Equinoxe · Сообщение **Equinoxe** » 14 июн 2011, 22:01

А я без перебора и единственности вот как решила:
Факт 1. прямоугольник 1х3 содержит не менее 1-ой клеточки. (т.к. иначе соседний 2х3 будет содержать целых 5, что нельзя)
Факт 2. прямоугольник 1х4, не пересекающий центральную клетку, содержит не более 2-х клеточек (в соседнем 3х4 с учетом 1-ого факта содержится не менее 6=5+1, а в каждом 4х4 строго 8. А 8-6=2)
Факт 3. прямоугольник 1х4 у края содержит не менее 2-х клеточек (т.е. ровно 2) (иначе, очевидно, соседний 1х4 переполнится)
Факт 4. в итоге должно быть ровно 13 клеточек (в центральной 3х3 ровно 5, остальное укладываем 1х4-ками)
Решение: в 4х4 должно быть 8, тогда в остальных должно быть 5. Видим, что угловая должна быть закрашена. Однако тогда не наберется 5-ти.

Всё ^_^

СергейП

Хорошо!
Только очень уж лаконично, разные люди читают. Надо бы поподробнее объяснить.
И еще из 1-3 следует что во всех полосках 1Х4 ровно по 2 закрашенных клетки.
Ну и еще не понял вывод

Equinoxe писал(а):Source of the post Решение: в 4х4 должно быть 8, тогда в остальных должно быть 5. Видим, что угловая должна быть закрашена. Однако тогда не наберется 5-ти.

Где не наберется 5?
Я из этих фактов 1-4 несколько другой вывод сделал, там совсем не так коротко, но строго все доказывается.
Так что это за 5-ка?

Equinoxe · Сообщение **Equinoxe** » 15 июн 2011, 13:00

СергейП писал(а):Source of the post
Хорошо!
Только очень уж лаконично, разные люди читают. Надо бы поподробнее объяснить.
И еще из 1-3 следует что во всех полосках 1Х4 ровно по 2 закрашенных клетки.

Вот здесь надо быть очень аккуратным. Док-во использует возможность поставить рядом 3х4 (т.е. продолжить до 4х4), из-за этого появляются ограничения (а именно, 1х4 не пересекает центральную клетку. Ведь только для таких 1х4 невозможно поставить рядом 3х4. Факт 3 точно также работает для всех кроме центральных, но в моём решении вообще нужны только крайние)

СергейП писал(а):Source of the post
Ну и еще не понял вывод
Equinoxe писал(а):Source of the post Решение: в 4х4 должно быть 8, тогда в остальных должно быть 5. Видим, что угловая должна быть закрашена. Однако тогда не наберется 5-ти.
Где не наберется 5?
Я из этих фактов 1-4 несколько другой вывод сделал, там совсем не так коротко, но строго все доказывается.
Так что это за 5-ка?

Факт 4 объясняет нам, что в сумме должно быть 13. Т.к. в квадратике 4х4 должно быть 8, в оставшихся клетках должно быть 13-8=5. Дальше всё совсем просто, используется 3-й факт — достаточно рассмотреть два непересекающихся 1х4 и понять, что придетсяя закрасить угловую клеточку, а затем понять, что если она закрашена, решение не существует

СергейП

Equinoxe писал(а):Source of the post
СергейП писал(а):Source of the post Хорошо!
Только очень уж лаконично, разные люди читают. Надо бы поподробнее объяснить.
И еще из 1-3 следует что во всех полосках 1Х4 ровно по 2 закрашенных клетки.
Вот здесь надо быть очень аккуратным. Док-во использует возможность поставить рядом 3х4 (т.е. продолжить до 4х4), из-за этого появляются ограничения (а именно, 1х4 не пересекает центральную клетку. Ведь только для таких 1х4 невозможно поставить рядом 3х4. Факт 3 точно также работает для всех кроме центральных, но в моём решении вообще нужны только крайние)

Здесь не нужна аккуратность. Все 1Х4 должны иметь ровно по 2 закраш. клетки. Это следует из того, что в 2Х4 всего 4 закрашенных, поэтому последовательно рассматривая соседние 1Х4, получаем 2Х4 и т.д. Доходим до края и последоват. получаем во всех 1Х4 по 2 такие клетки.

Equinoxe писал(а):Source of the post Факт 4 объясняет нам, что в сумме должно быть 13. Т.к. в квадратике 4х4 должно быть 8, в оставшихся клетках должно быть 13-8=5. Дальше всё совсем просто, используется 3-й факт — достаточно рассмотреть два непересекающихся 1х4 и понять, что придетсяя закрасить угловую клеточку, а затем понять, что если она закрашена, решение не существует

Да, угловые закрашены, между ними по 1 закрашенной клетке. Всего на 2 смежных краях 5 клеток. Доказательство еще надо демонстрировать.

Equinoxe · Сообщение **Equinoxe** » 15 июн 2011, 14:15

СергейП писал(а):Source of the post
Здесь не нужна аккуратность. Все 1Х4 должны иметь ровно по 2 закраш. клетки. Это следует из того, что в 2Х4 всего 4 закрашенных, поэтому последовательно рассматривая соседние 1Х4, получаем 2Х4 и т.д. Доходим до края и последоват. получаем во всех 1Х4 по 2 такие клетки.

Сууупер! Тогда всё воообще просто:
Выкладываем из трёх 1х4 прямоугольник 3х4, в нём — 2*3=6. Но в 3х3 — 5, значит, в крайних 1х3 ровно 6-5=1.
Выходит во всех 1х3, не пересекающих центральную клетку, ровно 1. Тогда в 1х3, пересекающей центральную, получится ровно 5-1-1=3. Но если в этой 1х3 — 3, то в соответствующей 1х4 точно больше 2х, противоречие!

СергейП

Equinoxe писал(а):Source of the post Выкладываем из трёх 1х4 прямоугольник 3х4, в нём — 2*3=6. Но в 3х3 — 5, значит, в крайних 1х3 ровно 6-5=1.
Выходит во всех 1х3, не пересекающих центральную клетку, ровно 1. Тогда в 1х3, пересекающей центральную, получится ровно 5-1-1=3. Но если в этой 1х3 — 3, то в соответствующей 1х4 точно больше 2х, противоречие!

А вот это очень хорошо!
У меня было продолжение док-ва по пп. 1-4, но там было долго и некрасиво. Сейчас совсем неплохо.

Между прочим, при покраске поля 4Х4 все это выполняется!
И во всех 1Х4 по 2 клетке, а в 1Х3 не в центральной зоне по 1 клетке.

BSK · Сообщение **BSK** » 15 июн 2011, 15:17

Equinoxe писал(а):Source of the post
СергейП писал(а):Source of the post
Здесь не нужна аккуратность. Все 1Х4 должны иметь ровно по 2 закраш. клетки. Это следует из того, что в 2Х4 всего 4 закрашенных, поэтому последовательно рассматривая соседние 1Х4, получаем 2Х4 и т.д. Доходим до края и последоват. получаем во всех 1Х4 по 2 такие клетки.

Сууупер! Тогда всё воообще просто:

Не сууупер, а ошибка.
В первом столбце не закрасим только среднюю клетку, во втором столбце закрасим только среднюю клетку и т.д. И всё будет в порядке для 2x4.

Equinoxe · Сообщение **Equinoxe** » 15 июн 2011, 15:23

BSK писал(а):Source of the post
Equinoxe писал(а):Source of the post
СергейП писал(а):Source of the post
Здесь не нужна аккуратность. Все 1Х4 должны иметь ровно по 2 закраш. клетки. Это следует из того, что в 2Х4 всего 4 закрашенных, поэтому последовательно рассматривая соседние 1Х4, получаем 2Х4 и т.д. Доходим до края и последоват. получаем во всех 1Х4 по 2 такие клетки.

Сууупер! Тогда всё воообще просто:

Не сууупер, а ошибка.
В первом столбце не закрасим только среднюю клетку, во втором столбце закрасим только среднюю клетку и т.д. И всё будет в порядке для 2x4.

Ваша мысль совершенно, увы, непонятна

Если мы доказали, что во всех крайних 1х4 будет ровно 2, то последовательно идя, мы будем получать 2-ки и во всех остальных 1х4. Тут всё действительно очевидно.

BSK · Сообщение **BSK** » 15 июн 2011, 15:27

Equinoxe писал(а):Source of the post
Ваша мысль совершенно, увы, непонятна

Если мы доказали, что во всех крайних 1х4 будет ровно 2, то последовательно идя, мы будем получать 2-ки и во всех остальных 1х4. Тут всё действительно очевидно.

В первом столбце не закрасим только среднюю клетку, во втором столбце закрасим только среднюю клетку и т.д.

Чего тут непонятного, где проблемы для 2 на 4?

yourdomain.com