Как покрыть корову№ 1
Носорог

Условия: на плоскости имеется квадратная корова со стороной 100. Из двух противоположных углов коровы удалили два квадратика со стороной 1. Итого, оставшаяся площадь коровы: 100*100-2=9998.
Имеются прямоугольные быки со сторонами 1 и 2. Таких быков - 4999. Их суммарная площадь, как легко видеть: 9998.
Задача: разработать алгоритм покрытия ВСЕЙ коровы быками. В случае невозможности, просьба обосновать
Профиль 

Как покрыть корову№ 2
MigaRU

Покрыть нет никакой возможности! Вот если бы с одной стороны уголки удалили, тогда - да, а так ничего у них не выйдет((. Потому что как этих быков ни крути, но они могут всегда покрыть только соседние клетки. Вот если представить себе эту корову в шахматном окрасе, то получается, что бык может покрыть одновременно две клетки обязательно разных цветов, а уголки то они одного цвета! Т.о. в корове содержиться на два белых пятна меньше, чем черных! И вот ничего у них и не выйдет, а жаль....
Профиль 

Как покрыть корову№ 3
Носорог

И мне жаль... , А ты умница, мне полдня думать пришлось
 
[ 01-09-07, Сбт, 22:41:11 Отредактировано: Носорог ]
Профиль 

Как покрыть корову№ 4
MigaRU

Просто коровы - моя тайная страсть))).
Профиль 

Как покрыть корову№ 5
Носорог

Чего ж ты в интернете рассказываешь, если "тайная!?"
Профиль 

Как покрыть корову№ 6
Вольфин

Чтобы покрыть корову нужен бык.
Профиль 

Как покрыть корову№ 7
Носорог

Автор: Носорог
Дата : 01-09-07, Сбт, 22:14:51
Имеются прямоугольные быки со сторонами 1 и 2...


Мало Вам, Вольфин?
Профиль 

Как покрыть корову№ 8
MigaRU

Вот усложненный вариант этой коровы:
доска 8*8, вырезан один уголок. Можно ли покрыть доминошками 1*3?
Профиль 

Как покрыть корову№ 9
MigaRU

Помогите задачку-то решить.
Профиль 

Как покрыть корову№ 10
Большой Грызь

Намекаю..

 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 

Как покрыть корову№ 11
MigaRU

УРЯЯЯЯ!! Вот оно что!!!
Профиль 

Как покрыть корову№ 12
Большой Грызь

Хорошо, когда понимают с полуслова
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 

Как покрыть корову№ 13
Носорог

Мне полслова - мало. В чем фишка-то?
Профиль 

Как покрыть корову№ 14
Большой Грызь

Для начала заметим, что на доске с вырезанным углом есть 63 клетки. Каждая доминошка покрывает три клетки. Следовательно для того, чтобы покрыть доску, нужна 21 доминошка.

Теперь обратим внимание на помеченные клетки. Если вся доска покрыта доминошками, то:
1) каждая помеченная клетка покрыта хотя бы одной доминошкой (т.е. нет клеток, которые не покрыты ни одной доминошкой вообще)
2) каждая помеченная клетка покрыта ровно одной доминошкой, ибо доминошки не перекрывают друг дружку (т.е. нет клеток, покрытых двумя доминошками)
3) каждая доминошка покрывает лишь одну помеченную клетку. Это доказывается легко - достаточно заметить, как именно помечены клетки.

Отсюда вывод: доминошек должно быть ровно столько же, сколько и помеченных клеток. Т.е. 22 штуки. Противоречие.
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 


Вы не зарегистрированы либо не вошли в портал!!!
Регистрация или вход в портал - в главном меню.



 Просмотров:   009646    Постингов:   000014