Шахматная доска и кости домино

и задачки для интервью.
User avatar
goldenstate
Уже с Приветом
Posts: 5340
Joined: 20 Jun 2012 23:36
Location: чемодан-вокзал-SFBA

Шахматная доска и кости домино

Post by goldenstate » 12 Oct 2012 22:36

Условия:
- шахматная доска с 64 полями.
- одна кость домино может закрыть два шахматных поля.
- естественно, нужно 32 костей домино, чтобы закрыть всю доску (64 поля).

Вопрос:
- если удалить два угловых поля по диагонали друг к другу на шахматной доске, то можно ли закрыть оставшиеся 62 поля с помощью 31-й кости?

User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Шахматная доска и кости домино

Post by rzen » 12 Oct 2012 22:37

Можно
Don't code today what you can't debug tomorrow.

User avatar
goldenstate
Уже с Приветом
Posts: 5340
Joined: 20 Jun 2012 23:36
Location: чемодан-вокзал-SFBA

Re: Шахматная доска и кости домино

Post by goldenstate » 13 Oct 2012 00:24

rzen wrote:Можно

Как насчет решения?

User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Шахматная доска и кости домино

Post by rzen » 13 Oct 2012 00:35

goldenstate wrote:
rzen wrote:Можно

Как насчет решения?

Вопрос был можно ли :-)
Don't code today what you can't debug tomorrow.

User avatar
Интеррапт
Уже с Приветом
Posts: 17281
Joined: 07 Sep 2011 10:05
Location: Seattle, WA

Re: Шахматная доска и кости домино

Post by Интеррапт » 13 Oct 2012 00:43

goldenstate wrote:Условия:
- шахматная доска с 64 полями.
- одна кость домино может закрыть два шахматных поля.
- естественно, нужно 32 костей домино, чтобы закрыть всю доску (64 поля).

Вопрос:
- если удалить два угловых поля по диагонали друг к другу на шахматной доске, то можно ли закрыть оставшиеся 62 поля с помощью 31-й кости?


Думаю, что нельзя. Потому что это шахматная доска, где две противоположные клетки на одной диагонали ведь будут одного цвета.

Image

Так что при вырезании получается, что клеток одного цвета на доске станет больше, чем другого (на две клетки). Еще и находятся на противоположных концах. Так что никак, сможете разместить только 30 костей.

User avatar
goldenstate
Уже с Приветом
Posts: 5340
Joined: 20 Jun 2012 23:36
Location: чемодан-вокзал-SFBA

Re: Шахматная доска и кости домино

Post by goldenstate » 13 Oct 2012 00:50

rzen wrote:
goldenstate wrote:
rzen wrote:Можно

Как насчет решения?

Вопрос был можно ли :-)

Математикам обычно без разницы какой ответ, им важно только решение. :-)

User avatar
goldenstate
Уже с Приветом
Posts: 5340
Joined: 20 Jun 2012 23:36
Location: чемодан-вокзал-SFBA

Re: Шахматная доска и кости домино

Post by goldenstate » 13 Oct 2012 00:56

Интеррапт wrote:
goldenstate wrote:Условия:
- шахматная доска с 64 полями.
- одна кость домино может закрыть два шахматных поля.
- естественно, нужно 32 костей домино, чтобы закрыть всю доску (64 поля).

Вопрос:
- если удалить два угловых поля по диагонали друг к другу на шахматной доске, то можно ли закрыть оставшиеся 62 поля с помощью 31-й кости?


Думаю, что нельзя. Потому что это шахматная доска, где две противоположные клетки на одной диагонали ведь будут одного цвета.

Image

Так что при вырезании получается, что клеток одного цвета на доске станет больше, чем другого (на две клетки).
Так, и что дальше. Я потерял Ваши рассуждения. Что из этого следует дальше?

Еще и находятся на противоположных концах.
Так, и что из этого следует?
Так что никак, сможете разместить только 30 костей.
А это из чего следует?

Hamster
Уже с Приветом
Posts: 11475
Joined: 20 Nov 2000 10:01
Location: Escondido, CA

Re: Шахматная доска и кости домино

Post by Hamster » 13 Oct 2012 00:57

Интеррапт wrote:Думаю, что нельзя. Потому что это шахматная доска, где две противоположные клетки на одной диагонали ведь будут одного цвета.

Так что при вырезании получается, что клеток одного цвета на доске станет больше, чем другого (на две клетки). Еще и находятся на противоположных концах. Так что никак, сможете разместить только 30 костей.


Можно переформулировать так. Допустим, что вырезаются черные клетки. Каждая кость закрывает максимум одну белую и максимум одну черную клетку. После вырезания на доске остается 32 белых клетки и 30 черных клеток. Чтобы накрыть 32 белых клетки, нужно 32 кости.

А вот если вырезать две угловых клетки на одной стороне (разных цветов), доска успешно накрывается 31 костью.
Протоукр

User avatar
goldenstate
Уже с Приветом
Posts: 5340
Joined: 20 Jun 2012 23:36
Location: чемодан-вокзал-SFBA

Re: Шахматная доска и кости домино

Post by goldenstate » 13 Oct 2012 01:04

Hamster wrote:
Интеррапт wrote:Думаю, что нельзя. Потому что это шахматная доска, где две противоположные клетки на одной диагонали ведь будут одного цвета.

Так что при вырезании получается, что клеток одного цвета на доске станет больше, чем другого (на две клетки). Еще и находятся на противоположных концах. Так что никак, сможете разместить только 30 костей.


Можно переформулировать так. Допустим, что вырезаются черные клетки. Каждая кость закрывает максимум одну белую и максимум одну черную клетку. После вырезания на доске остается 32 белых клетки и 30 черных клеток. Чтобы накрыть 32 белых клетки, нужно 32 кости.

А вот если вырезать две угловых клетки на одной стороне (разных цветов), доска успешно накрывается 31 костью.
:good: Верно!

Если убрать 2 поля одного цвета, то на доске все-равно останется 32 поля другого цвета, а значит их никак нельзя будет закрыть 31-й костью!

Теперь идем пить пиво - пятница, конец недели!

User avatar
Интеррапт
Уже с Приветом
Posts: 17281
Joined: 07 Sep 2011 10:05
Location: Seattle, WA

Re: Шахматная доска и кости домино

Post by Интеррапт » 13 Oct 2012 01:16

Hamster wrote:
Интеррапт wrote:Думаю, что нельзя. Потому что это шахматная доска, где две противоположные клетки на одной диагонали ведь будут одного цвета.

Так что при вырезании получается, что клеток одного цвета на доске станет больше, чем другого (на две клетки). Еще и находятся на противоположных концах. Так что никак, сможете разместить только 30 костей.


Можно переформулировать так. Допустим, что вырезаются черные клетки. Каждая кость закрывает максимум одну белую и максимум одну черную клетку. После вырезания на доске остается 32 белых клетки и 30 черных клеток. Чтобы накрыть 32 белых клетки, нужно 32 кости.

А вот если вырезать две угловых клетки на одной стороне (разных цветов), доска успешно накрывается 31 костью.


Ага. Собственно это я и имел в виду, только обьяснил неудачно.

User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Шахматная доска и кости домино

Post by rzen » 13 Oct 2012 02:05

Сыплю голову пеплом, действительно нельзя. А "в слепую" показалось что можно.
Don't code today what you can't debug tomorrow.

User avatar
goldenstate
Уже с Приветом
Posts: 5340
Joined: 20 Jun 2012 23:36
Location: чемодан-вокзал-SFBA

Re: Шахматная доска и кости домино

Post by goldenstate » 13 Oct 2012 02:18

Интеррапт wrote:
Hamster wrote:
Интеррапт wrote:Думаю, что нельзя. Потому что это шахматная доска, где две противоположные клетки на одной диагонали ведь будут одного цвета.

Так что при вырезании получается, что клеток одного цвета на доске станет больше, чем другого (на две клетки). Еще и находятся на противоположных концах. Так что никак, сможете разместить только 30 костей.


Можно переформулировать так. Допустим, что вырезаются черные клетки. Каждая кость закрывает максимум одну белую и максимум одну черную клетку. После вырезания на доске остается 32 белых клетки и 30 черных клеток. Чтобы накрыть 32 белых клетки, нужно 32 кости.

А вот если вырезать две угловых клетки на одной стороне (разных цветов), доска успешно накрывается 31 костью.


Ага. Собственно это я и имел в виду, только обьяснил неудачно.
Я догадывался, что Вы имели ввиду, но не был уверен. Вобщем тогда Вам тоже можно пива.

User avatar
goldenstate
Уже с Приветом
Posts: 5340
Joined: 20 Jun 2012 23:36
Location: чемодан-вокзал-SFBA

Re: Шахматная доска и кости домино

Post by goldenstate » 13 Oct 2012 02:20

rzen wrote:Сыплю голову пеплом, действительно нельзя. А "в слепую" показалось что можно.
В слепую ответ иногда бывает даже правильнее, чем с решением. Но все дело как раз в решении. С вас интересная головоломка, и тогда мы ее отгадываем вместе за пивом.

User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Шахматная доска и кости домино

Post by rzen » 13 Oct 2012 02:44

Чувака заперли в комнате. Две двери. Через первую выход в комнату с увеличительным стеклом в потолке. Солнце сжигает всё живое. Через вторую комната с огнедышащим драконом.

Других выходов нет.

Как чуваку сбежать?
Don't code today what you can't debug tomorrow.

User avatar
goldenstate
Уже с Приветом
Posts: 5340
Joined: 20 Jun 2012 23:36
Location: чемодан-вокзал-SFBA

Re: Шахматная доска и кости домино

Post by goldenstate » 13 Oct 2012 03:05

rzen wrote:Чувака заперли в комнате. Две двери. Через первую выход в комнату с увеличительным стеклом в потолке. Солнце сжигает всё живое. Через вторую комната с огнедышащим драконом.

Других выходов нет.

Как чуваку сбежать?

Выйти через комнату с увеличительным стеклом, но ночью.

User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Шахматная доска и кости домино

Post by rzen » 13 Oct 2012 03:09

goldenstate wrote:
rzen wrote:Чувака заперли в комнате. Две двери. Через первую выход в комнату с увеличительным стеклом в потолке. Солнце сжигает всё живое. Через вторую комната с огнедышащим драконом.

Других выходов нет.

Как чуваку сбежать?

Выйти через комнату с увеличительным стеклом, но ночью.

Правильно. Видимо хорошее пиво :-)

А мне уже можно? :-)
Don't code today what you can't debug tomorrow.

Zorkus
Уже с Приветом
Posts: 6969
Joined: 26 Feb 2011 17:40

Re: Шахматная доска и кости домино

Post by Zorkus » 13 Oct 2012 03:16

Заманить дракона в комнату со стеклом чтобы зажарился, потом спокойно уйти. Как заманить его туда - это уже мелочь и деталь реализации.

Zorkus
Уже с Приветом
Posts: 6969
Joined: 26 Feb 2011 17:40

Re: Шахматная доска и кости домино

Post by Zorkus » 13 Oct 2012 03:17

Первая задача про шахматы- классический брейнтизер на интервью. Меня его раза два или три спрашивали.

User avatar
goldenstate
Уже с Приветом
Posts: 5340
Joined: 20 Jun 2012 23:36
Location: чемодан-вокзал-SFBA

Re: Шахматная доска и кости домино

Post by goldenstate » 13 Oct 2012 07:39

Zorkus wrote:Первая задача про шахматы- классический брейнтизер на интервью. Меня его раза два или три спрашивали.

Серьезно? Ну блин я не знал, сорри. Поделитесь еще Вашими головоломками.

User avatar
Helmsman
Уже с Приветом
Posts: 5059
Joined: 15 May 2003 00:04
Location: LA

Re: Шахматная доска и кости домино

Post by Helmsman » 13 Oct 2012 07:41

Ага, ему лет больше, чем многим из нас.

User avatar
goldenstate
Уже с Приветом
Posts: 5340
Joined: 20 Jun 2012 23:36
Location: чемодан-вокзал-SFBA

Re: Шахматная доска и кости домино

Post by goldenstate » 13 Oct 2012 07:44

rzen wrote:
goldenstate wrote:
rzen wrote:Чувака заперли в комнате. Две двери. Через первую выход в комнату с увеличительным стеклом в потолке. Солнце сжигает всё живое. Через вторую комната с огнедышащим драконом.

Других выходов нет.

Как чуваку сбежать?

Выйти через комнату с увеличительным стеклом, но ночью.

Правильно. Видимо хорошее пиво :-)

А мне уже можно? :-)
О ё моё, я про Вас совсем забыл... МОжно уже можно. Там, в холодильнике наверно холодненькое есть. Головоломка была хорошая, я честно слышал в первый раз.

User avatar
rzen
Уже с Приветом
Posts: 24375
Joined: 18 Nov 2003 16:42

Re: Шахматная доска и кости домино

Post by rzen » 13 Oct 2012 14:59

goldenstate wrote:
rzen wrote:
goldenstate wrote:
rzen wrote:Чувака заперли в комнате. Две двери. Через первую выход в комнату с увеличительным стеклом в потолке. Солнце сжигает всё живое. Через вторую комната с огнедышащим драконом.

Других выходов нет.

Как чуваку сбежать?

Выйти через комнату с увеличительным стеклом, но ночью.

Правильно. Видимо хорошее пиво :-)

А мне уже можно? :-)
О ё моё, я про Вас совсем забыл... МОжно уже можно. Там, в холодильнике наверно холодненькое есть. Головоломка была хорошая, я честно слышал в первый раз.

Ну вот, пришлось вчера ограничиться вином :-)

:beer:
Don't code today what you can't debug tomorrow.

User avatar
Trespassers W
Уже с Приветом
Posts: 7841
Joined: 04 Dec 2003 06:55
Location: USA

Re: Шахматная доска и кости домино

Post by Trespassers W » 04 Feb 2013 21:11

goldenstate wrote:
Zorkus wrote:Первая задача про шахматы- классический брейнтизер на интервью. Меня его раза два или три спрашивали.

Серьезно? Ну блин я не знал, сорри. Поделитесь еще Вашими головоломками.

Ага, решение этой задачи как пример математического доказательства приводит Саймон Сингх в своей книге про теорему Ферма:
- Оба угловых поля, выпиленные из доски, — белые. Следовательно на доске остались 32 черных поля и только 30 белых поля.
- Каждое домино покрывает два смежных поля, а смежные поля всегда отличаются по цвету, т.е. одно поле черное, а другое — белое.
- Следовательно, независимо от расположения домино на шахматной доске, первые 30 костей, выложенных на доску, должны покрыть 30 белых и 30 черных полей.
- Это означает, что при любом раскладе всегда останется одна домино и два непокрытых черных поля.
- Но любая кость домино покрывает на шахматной доске два смежных поля, а смежные поля всегда отличаются по цвету. Два оставшихся непокрытыми поля одного цвета, и поэтому накрыть их одной костью домино невозможно. Следовательно, покрыть эту доску 31 костью домино невозможно!


Если еще не читали, то бегом читать:

Сначала эту: Fermat's Enigma
Потом эту: The Code Book

Вот тут есть на русском: ВЕЛИКАЯ ТЕОРЕМА ФЕРМА

Обе книги - супер! Невозможно оторваться.
Как кому, а мне нравится думать! М.Жванецкий

Return to “Головоломки”