Квадратная доска 6x6 заполнена костяшками домино 1x2. Докажите, что можно провести вертикальный или горизонтальный разрез этой доски, не пересекающий ни одной из костяшек домино.
Ответ: Данную доску можно разрезать на два прямоугольника 10 способами (5 вертикальных разрезов и 5 горизонтальных). Если при этом задеваются всякий раз костяшки домино, то при каждом разрезе мы должны разрезать хотя бы две костяшки. При этом различными разрезами разрезаем различные костяшки, т. е. число разрезаемых костяшек будет 10*2 = 20, а всего костяшек - 18. Противоречие. Значит, хотя бы один разрез не задевает ни одной костяшки домино.
Комментарии
что за бред нарисуй хотя бы то что написал и посмотри никаких проблем с разрезами нет, как хочешь так и реж
нет тут бреда, ты доминошки по разному располагай и поймешь...
я вроде её сделал, смотрю ответ, а тут пурга, правы люди, предлагаю свой вариант...
То есть, если расставлять вертикально домино так, чтобы поперек каждой линии встала хотя бы одна фишка, то их 5, каждая фишка таким образом вынуждает поставить с одной стороны еще одну фишку вертикально, т. к. с одной из сторон остается нечетное число клеток, что делает невозможным постановку фишки горизонтально с этой стороны на этой строке.
То есть, фишки, расставленные по нужному нам принципу занимают 5+5 = 10 клеток.
Если расставлять отсавшиеся фишки горизонтально по такому же принципу, то им необходимо так же 10 клеток. Но осталось только 8, что делает невозможным такую расстановку.
Ура, наконецто, а теперь смотреть ответ
ДЛя того, чтобы расставить костяшки нужным макаром напрягаться не нужно - заполни два столбца, как предлагаешь - по 5 в высоту и одни - поперёк, или как-нибудь по-другому, и рядом - такой же, между ними и будет требуемая тебе..., в-общем, сам понимаешь. А задача - доказать, что при ЛЮБОМ расположении костяшек, а не ВОЗМОЖНО ли
совершенно верно
Полная шляпа. Без визуализации все ваши головоломки никому не нужны.
мдя комменты на задачу))))
ничего лишнего.
все прекрасно описано!
спасибо !
просьба визуализировать!
Доказательство неверно, так как можно провести линию и разрезать только одну доминошку. Скажем вариант, когда в середине доски все доминошки находятся горизонательно и состыкованы друг с другом по одной вертикальной линии, а одна доминошка линией разрезается.
Тоесть задача определенно имеет решение, но представленное в ответе решение не верно.
Аллёээээээээ!
ДЛя начала можно было бы задуматься - а что значит "хотя бы 2 костяшки", а там - и готово! Решение - исчерпывающее
Доказательство верно, только там присутствует один не совсем понятный момент. Почему каждый разрез должен захватывать как минимум две костяшки? Докажем это как лемму. Предположим противное, т. е. что разрез захватил только одну костяшку. Тогда по каждую сторону от разреза (минус поле от разрезанной костяшки) остаётся нечётное число клеток, которые должны быть полностью заполнены костяшками, что невозможно.
"Тогда по каждую сторону от разреза (минус поле от разрезанной костяшки) остаётся нечётное число клеток, которые должны быть полностью заполнены костяшками, что невозможно."
Во-первых, не по каждую сторону, а только по одну, т.к. любое нечётное число (в данном случае 5) = нечётное число + чётное. А во-вторых, и нечётное число можно выложить костяшками 1х2 - для этого некоторые нужно положить торцом (короткой стороной в одну клетку) к разрезу.
Решение задачи при этом рассыпается.
Александр все верно доказал, "по каждую сторону от разреза... остаётся нечётное число клеток".
Речь идет применительно ко всей доске в 36 клеток, где любой разрез делит ее на две области с четными числами клеток, "в данном случае" Вашем, когда разрез по центру через одну домино, получается с двух сторон по 17 свободных клеток.
Правильное замечание.
ЧЁ ТУТ СЛОЖНОГО ПРИ ПРАВИЛЬНОМ РАСПОЛОЖЕНИИ КОСТЯШЕК НИ ОДНА ИЗ НИХ НЕ ПОСТРАДАЕТ!!!!!!
!!!! !!!!
!!!! !!!!
!!!! !!!!
!!!! !!!!
!!!! !!!!
!!!! !!!!
идиот
суть задачи - доказать, что при абсолютно любом расположении костей найдётся такая линия, которая не пересечёт ни одну костяшку
ещё раз повторю: "при абсолютно любом", а не при "правильном"
затупить, и думать, что ты самый умный, ну это просто верх идиотизма
Вообще-то резать, чтобы ничего не задеть, придется наноинструментом с офигенной точностью.
Толщину реза никто не учитывает
А кто тебе сказал, что размер домино совпадает с размером клеток доски? :)
Отличная задача! Очень изящная
Предложу свой способ) Правда не совсем строгий.
Изначально договоримся, что считать горизонтальным направлением доски, а что - горизонтальным. Рассмотрим горизонтальное направление (т.е первоначальное положение доски). Расположим пять доминошек так, чтобы каждый вертикальный разрез резал одну доминошку. Назовем это расстановкой Р1. Аналогично сделаем для вертикального направления (т.е повернем доску на 900 и проделаем ту же операцию), причем доминошки можно расположить без взаимных пересечений (*). Назовем инверсией расстановки остальную расстановку доминошек (оставшихся 31 = 36-5). Понятно, что при правильном расположении инверсии расстановок Р1 и Р2 совпадают при повороте одной из них на 90 градусов. Получается, то и расстановки Р1,2 переходят друг в друга при том же повороте. Очевидно, что без пересечений такое невозможно. Значит расстановка по алгоритму (*) невозможна
*В самом начале: "что считать вертикальным, а что - горизонтальным..."
1.Условие задачи сформулировано неоднозначно, а именно: "Квадратная доска 6x6 заполнена костяшками домино 1x2." Например, если доска заполнена не полностью, то легко показать, что условие не выполняется (см. рис.). 2.Доказательство утверждения "при каждом разрезе мы должны разрезать хотя бы две костяшки" отсутствует. А данное утверждение не очевидно...Не понятно, как здесь вставлять рисунки...