Логика для всех

  Все выпуски  

Логика для всех


Служба Рассылок Subscribe.Ru проекта Citycat.Ru

"Логика для всех" выпуск No26 oт 2001-07-05

 

Здравствуйте!


Четыре подруги и домино

Однажды вечером четыре задушевные подруги (назовем их Алиса, Виолетта, Светлана и Диана), устав от бесконечных многолюдных вечеринок, решили скоротать вечер в уютной домашней обстановке. К сожалению, именно в этот вечер в доме не было электричества :-). Не было возможности смотреть телевизор, слушать музыку, играть на компьютере... Пригорюнились милые девушки, склонили свои прелестные личики, тускло освещаемые неровным пламенем свечей... Тут одна из них вспомнила, что пасьянс можно раскладывать с помощью обычной колоды карт, а не только на компьютере. Хозяйка погруженной в полумрак квартиры вытащила верхний ящик из комода и вывалила все его содержимое на стол. Но карт там не оказалось... Но удалось обнаружить интересную коробочку с надписью "ДОМИНО". Что означало это загадочное слово девушки не знали, поэтому поспешили открыть коробочку. Разумеется, внутри они нашли 28 пластиковых прямоугольников черного цвета, с поперечной бороздкой посередине каждой. Что делать дальше с этими приятными на ощупь "безделушками" и почему на некоторые квадратики были нанесены белые точки,  никто не знал, а инструкцию на дне коробки заметили не сразу :). А когда заметили, внимательно прочитали и решили следовать описанию самой простейшей игры.

Сначала девушки аккуратно перевернули всех костяшки вниз точками, тщательно перемешали и распредeлили между собой поровну (по 7 каждой). Первый ход делала Алиса, за ней Виолетта, а потом Светлана и Диана. Костяшки укладывались в прямую цепочку так, что бы количество точек на одной из половинок домино совпадало с количеством точек на одном из свободных концов выстроенной цепочки.

Сумма всех точек на двух первых костяшках для каждой из девушек:

Алиса: 23
Виолетта: 20
Светлана: 18
Диана: 16

Свой третий ход Алиса сделала с костяшкой 6-2.

В какой последовательности были выложены первые восемь костяшек домино?


GRAND CHAIN

(CALIBAN'S PROBLEM BOOK: Mathematical, Inferential and Cryptographic Puzzles
by Hubert Phillips (Caliban), S.T. Shovelton and G. Struan Marshall, problem 2)

Alice, Betty, Clara, and Dolly are playing a simple game with a set of 28 dominoes. they have seven dominoes each to begin with, and, starting with Alice, take turns (in the order set out above) in the building of a chain.

It is a condition than one end of each domino played must be numerically identical with one of the open ends of the chain that is being built.

The total "pip values" of the first two dominoes played by each are:

  • Alice's two dominoes: 23
  • Betty's two dominoes: 20
  • Clara's two dominoes: 18
  • Dolly's two dominoes: 16

On the third round, Alice plays the 6-2.

What, in sequence, are the first eight dominoes played?


Solution

Alice's two dominoes totalling 23 must have been 6-6 and 6-5,
Betty's two dominoes totalling 20 must have been 6-4 and 5-5,
Clara's two dominoes totalling 18 must have been 6-3 and 5-4,
Dolly's two dominoes totalling 16 must have been 5-3 and 4-4,
since the 6-2 is in Alice's hand.

Alice cannot begin by playing the 6-6, for if she does, Betty must play the 6-4, Clara, the 6-3, and Dolly either the 3-5 or the 4-4. No piece can be played after the 4-4, and only one after the 3-5.

Therefore Alice must lead off with the 6-5, and the play is necessarily as follows:


                    1st round   2nd round

           Alice       6-5         6-6
           Betty       5-5         6-4
           Clara       5-4         6-3
           Dolly       4-4         5-3

Ответы и решения прислали:

  1. Александр
  2. Ksenia Vasilenko
  3. Паша - inferno (Долгопрудный)
  4. Асеев Денис
  5. Джибладзе Юрий (Саранск)
  6. Панина Галина
  7. Василий Славутинский (Москва)
  8. Сумароков Стас (Новгород)
  9. Вера Данилина (Москва)
  10. Ольга (Пермь)

Александр:

Обозначим имена Алиса, Виолетта, Светлана и Диана буквами A, B, C, D

Сумма первых двух фишек равна: A = 23, B = 20, C = 18, D = 16.

Из этого следует, что A владеет фишками 6:6 и 6:5, т.к. это единственная комбинация, дающая такую сумму. Откинув эти фишки, приходим к выводу, что B имеет фишки 6:4 и 5:5, т.к. опять же, это единственный вариант. По той же причине C распоряжается фишками 6:3 и 5:4. Сумму 16 для D мы можем получить только фишками 4:4 и 3:5.

Ходы обозначим буквой и цифрой (буква - кто, цифра - номер хода):

6:6(A1) - 6:4(B1) - 4:5(C1) - 5:3(D1) - 3:6(C2)
 |
6:5(A2) - 5:5(B2) - 5:3(D2)

Далее фишкой 6:2


Ksenia Vasilenko:

Очевидно, что за два первых хода Алиса выложила костяшки 6-6 и 6-5, Виолетта - 5-5 и 6-4, Светлана - 5-4 и 6-3, а Диана - 4-4 и 3-5 (могла бы быть 6-2, но, как мы знаем, она вышла только на 3-м ходy). Девушки клали костяшки в такой последовательности:

                |6-5|
                |6-5|5-5|
                |6-5|5-5|5-4|
                |6-5|5-5|5-4|4-4|
            |6-6|6-5|5-5|5-4|4-4|
            |6-6|6-5|5-5|5-4|4-4|4-6|
        |3-6|6-6|6-5|5-5|5-4|4-4|4-6|
    |5-3|3-6|6-6|6-5|5-5|5-4|4-4|4-6|
    |5-3|3-6|6-6|6-5|5-5|5-4|4-4|4-6|6-2|

Паша:

Вот таблица сумма очков - соответствующие костяшки домино.

    12 - [6-6]
    11 - [6-5]
    10 - [6-4][5-5]
     9 - [6-3][5-4]
     8 - [6-2][5-3][4-4]
     7 - [6-1][5-2][4-3]
     6 - [6-0][5-1][4-2][3-3]
     5 -      [5-0][4-1][3-2]
     4 -           [4-0][3-1][2-2]
     3 -                [3-0][2-1]
     2 -                     [2-0][1-1]
     1 -                          [1-0]
     0 -                               [0-0]

Из неё видно что у Алисы сумма 23 может быть только как 23 = 12+11 = [6-6]+[6-5], причём у всех оставшихся костяшек сумма не больше десяти.
Следовательно, у Виолетты 20 = 10+10 = [6-4]+[5-5], остались доминошки с суммой не больше девяти...
У Светланы 18 = 9+9 = [6-3]+[5-4], остались костяшки с суммой меньшей или равной восьми...
У Дианы 16 = 8+8 = [5-3]+[4-4] (так как [6-2] у Алисы, она ею на третьем ходу походит)

Начнём с конца. ПостПоследний ход сделала Алиса - [6-2]. Так как до этого цифры два на столе не было, то ход был сделан так:
          A3
????????[6-2]

Предыдущий ход Диана делала с другого конца (у неё нету 6), и из соображений чётности ясно, что это была костяшка [5-3] (так как сумма 23+20+28+26 нечётна, а на одном из концов цепочки уже стоит известная цифра 6). Кроме того, цифра 3 не может быть на свободном конце, так как тогда в середине цепочки была бы всего одна цифра 3 - в костяшке [6-3]. Следовательно,

  D2   C2         A3
[5-3][3-6]??????[6-2]

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

Пусть, для определённости Bиолетта вторым ходом ложит костяшку слева. Тогда

     B2   D1   C1     A2
-6][6-4][4-4][4-5]??[?-6][6-

Первые две костяшки уложить лишь следующим образом:

     B1   A1   A2
-5][5-5][5-6][6-

Итак, полностью решение выглядит следующим образом:

Ответ:
              D2   C2   B2   D1   C1   B1   A1   A2   A3
            [5-3][3-6][6-4][4-4][4-5][5-5][5-6][6-6][6-2]

              D2   C2   A2   A1   B1   C1   D1   B2   A3
            [5-3][3-6][6-6][6-5][5-5][5-4][4-4][4-6][6-2]

Асеев Денис:

Обозначим:

Алиса - А,
Виолетта - В,
Светлана - С,
Диана - Д.

А: сумма точек на первых двух использованных костяшках - 23.
   Максимальная сумма точек на одной костяшке 12 (или 6/6),
   поэтому вторая костяшка должна содержать 11 (или 5/6) точек.

В: сумма точек на первых двух использованных костяшках - 20.
   Данному варианту соответствуют 10 и 10, 9 и 11, 8 и 12.
   Последнии два варианта отпадают, т.к. кости 11 и 12 у А.
   10 и 10 - это 5/5 и 4/6.

С: сумма точек на первых двух использованных костяшках - 18.
   Данному варианту соответствуют 9 и 9. Другие варианты отпадают.
   9 и 9 - это 4/5 и 3/6.

Д: сумма точек на первых двух использованных костяшках - 16.
   Данному варианту соответствуют 8 и 8. Другие варианты отпадают.
   8 и 8 - это 4/4 и 3/5, кость 2/6 у А.

Возможных вариантов разложения первых восьми костей два:

Д2      С2      В2      Д1      С1      В1      А1      А2
5/3     3/6     6/4     4/4     4/5     5/5     5/6     6/6
и
В2      Д1      С1      В1      А1      А2      С2      Д2
6/4     4/4     4/5     5/5     5/6     6/6     6/3     3/5


Василий Славутинский:

Сначала задача кажется сложней. Но потом становится ясно, что такие большие суммы на двух костяшках реализyются очень небольшим числом вариантов.
Итак, A, B, C, D - участники, S(E,k) - сумма игрока E в k ходах. Остальные обoзначения
ясны из контекста.

S(A,2) = 23
S(B,2) = 20
S(C,2) = 18
S(D,2) = 16

Сумма на 1 костяшке  | 12 | 11 | 10       | 9          | 8
-------------------------------------------------------------------
Реализации           | 66 | 65 | 64  55   | 63  54     | 44 53 62

Каждая из двух цифр реализации есть количество точек на одной стороне костяшки.

Тогда
S(A,2) = 23 = 12 + 11 = 66,65 (и костяшки 66, 65 ушли)
S(B,2) = 20 = 10 + 10 = 64,55
S(C,2) = 18 = 9 + 9 = 63,54
S(D,2) = 16 = 8 + 8 = 44,53 (62 не может участвовать, т.к. была положена А третьим ходом)

Отметим, что суммы меньше 23 могут быть реализованы и другими вариантами, но, например,
у В не может быть костяшек 66 и 65, т.к. они непременно должны быть у А. И так далее.

Получаем

A 66,65
B 64,55
C 63,54
D 44,53

Дальше - ничего не остается - строим дерево вариантов,
узлом дерева будет конструкция "Х nn (NN)",
где X - участница игры,
nn - выложенная ей костяшка,
NN - значения конечных элементов цепочки.
Т.е. для цепочки, например, 12 23 34 45 56 это будет (16).
Х значит, что следующему игроку нечего положить.

                                  /\
                                 /  \
                                /    \
                               /      \
                              /        \
                             /          \
                            /            \
                           /              \
                          /                \
                         /                  \
                        /                    \
                       /                      \
                      /                        \
                     /                          \
                    /                            \
                   /                              \
                  /                                \
               A66(66)                            A65(65)
                 |                                 /\
                 |                                /  \
                 |                               /    \
                 |                              /      \
                 |                             /        \
                 |                            /          \
                 |                           /            \
                 |                          /              \
                 |                         /                \
                 |                        /                  \
                 |                       /                    \
                 |                      /                      \
              B64(64)               B64(54)                  B55(65)
                /\                    /\                             /\
               /  \                  /  \                           /  \
              /    \                /    \                         /    \
             /      \              /      \                       /      \
            /        \            /        \                     /        \
           /          \          /          \                   /          \
          /            \        /            \                 /            \
         /              \      /              \               /              \
     C63(34)         C54(65) C54(55)         C54(44)       C63(53)          C54(64)
        /\              |      |               |            /\                |
       /  \             |      |               |           /  \               |
      /    \            |      |               |          /    \              |
     /      \           |      |               |         /      \             |
    /        \          |      |               |        /        \            |
   /          \         |      |               |       /          \           |
D44(34)     D53(45)  D53(45) D53(53)         D44(44) D53(55)    D53(33)     D44(64)
  |            |        |      |               |      |           |           |
  |            |        |      |               |      |           |           |
  |            |        |      |               |      |           |           |
  |            |        |      |               |      |           |           |
  |            |        |      |               |      |           |           |
  |            |        |      |               |      |           |           |
  X         A65(46)   A65(53)  X               X      X           X        A66(64)
               |        |                                                     /\
               |        |                                                    /  \
               |        |                                                   /    \
               |        |                                                  /      \
               |        |                                                 /        \
               |        |                                                /          \
               X      B55(53)                                         B64(44)     B64(66)
                        |                                                |           |
                        |                                                |           |
                        |                                                |           |
                        |                                                |           |
                        |                                                |           |
                        |                                                |           |
                     C63(56)                                             X         C63(63)
                        |                                                            |
                        |                                                            |
                        |                                                            |
                        |                                                            |
                        |                                                            |
                        |                                                            |
                        X                                                          D53(65)
                                                                                     |
                                                                                     |
                                                                                     |
                                                                                     |
                                                                                     |
                                                                                     |
                                                                                  A62(52)

(И вот, наконец, А положила 62 третьим ходом)

Вот и все.
Ответ: A65 B55 C54 D44 A66 B64 C63 D53 A62

Конечно, смотрится это дерево громоздко, но поверьте, что на бумаге все это намного компактней. Собственно, нарисовать это на компьютере заняло намного больше времени, чем просто его составить %)


Вера Данилина:

Эта задача заставила меня некоторое время помучиться, хотя проблемы преимущественно возникали при разработке алгоритма решения. Было неясно, с чего лучше начать. Простой подбор костяшек согласно указанным суммам казался утомительным и бесперспективным, но когда я все-таки избрала этот путь, перебор занял не более 5 минут. Вот уж поистине: у страха глаза велики :). Хотя мое решение, по-видимому, не является наиболее рациональным, а может быть и нет.

Итак, решение.

Шаг 1-й.
Как было сказано, начала я с подбора возможных комбинаций.

Для Алисы (А): 23
получается единственное возможным способом 6-6, 6-5.

Для Виолетты (В): 20
получается следующими способами 6662, 6653, 6644, 6554, 5555
Но 6662, 6653, 6644 дублируют набор А, а 5555 в домино просто невозможно.
Остается 6-4, 5-5

Для Светланы (С): 18
6660, 6651, 6642, 6633, 6552, 6543
Из них подходит лишь комбинация 6543, т.к. остальные содержат те же костяшки, что у А и В (не забыть про третий ход А: 6-2), либо дублируются (6633 можно разложить на две одинаковых костящки 6-3, что невозможно).
Остается 6-3, 5-4.

И, наконец, Диана (Д): 16
6640, 6631, 6622, 6550, 6541, 6532, 6442, 6433, 5551, 5542, 5533, 5443.
Подходит только 1 комбинация: 4-4, 5-3.

Шаг 2-й.
Вторую часть решения проще представить в виде графа:

ход

    A       6-6                     6-5
           [6-6]                   [6-5]
    B       6-4                     6-4             5-5
           [6-4]                   [4-5]           [6-5]
    C       6-3             4-5     4-5             4-5             6-3
           [3-4]           [6-5]   [4-4]   [5-5]   [6-4]           [3-5]
    D       4-4     5-3     5-3     4-4     5-3     4-4             3-3     5-5
           [3-4]   [5-4]   [6-3]   [4-4]   [5-3]   [6-4]
    A               6-5     6-5                     6-6
                   [6-4]   [5-3]                   [6-4]
    B                       5-5                     6-4
                           [5-3]                   [6-6]    [4-4]
    C                       6-3                     6-3
                           [5-6]                   [6-3]
    D                                               5-3
                                                   [6-5]
    A                                               6-2

В квадратных скобках указаны цифры на концах цепочки после хода.

Следовательно, игра выглядела следующим образом:

А 6-5
В 5-5
С 4-5
Д 4-4
А 6-6
В 6-4
С 6-3
Д 5-3
А 6-2


Ольга:

Так как Алиса при первых двух костяшках набрала 23 точки - единственный вариант данной раскладки 6/6 и 6/5 (23 в сумме), причем третья костяшка была 6/2. Второй ходы делала Виолетта варианты костяшек для нее тоже единственные, исходя из начальных условий и костяшек Алисы имеем 6/4 и 5/5 (20 в сумме). Светлана ход делала третьей и сумма у нее, по условиям, 1 предполагаем вариант как 6/3 и 4/5. Вариант для Дианы остается такой 5/3 и 4/4.

В итоге раскладка была такая:
Алиса
6/5
Алиса-Виолетта
6/5_5/5
Алиса-Виолетта-Светлана
6/5_5/5_5/4
Алиса-Виолетта-Светлана-Диана
6/5_5/5_5/4_4/4
Алиса-Виолетта-Светлана-Диана-Алиса
6/6_6/5_5/5_5/4_4/4
Алиса-Виолетта-Светлана-Диана-Алиса-Виолетта
6/6_6/5_5/5_5/4_4/4_4/6
Алиса-Виолетта-Светлана-Диана-Алиса-Виолетта-Светлана
3/6_6/6_6/5_5/5_5/4_4/4_4/6
Алиса-Виолетта-Светлана-Диана-Алиса-Виолетта-Светлана-Диана
5/3_3/6_6/6_6/5_5/5_5/4_4/4_4/6
Алиса-Виолетта-Светлана-Диана-Алиса-Виолетта-Светлана-Диана-Алиса
5/3_3/6_6/6_6/5_5/5_5/4_4/4_4/6_6/2


До новой рассылки!

 

  Вопросы, пожелания и замечания пишите на ntl@yandex.ru.

Natalia

  http://ntl.narod.ru/logic - Логика для всех

  http://www.webboard.ru/wb.php?board=8701 - Головоломный форум

Использование материалов рассылки без согласования с ведущим рассылки не одобряется.

 

Приглашаю к сотрудничеству рекламодателей и спонсоров.

Архив Рассылки Рассылка 'Логика для всех' TopList SpyLOG Статистика Рассылки


http://subscribe.ru/
E-mail: ask@subscribe.ru
Отписаться Рейтингуется SpyLog

В избранное