30 авг. 2016 г.

Задачка про чаепитие

Добрый день.

Как уже иногда бывало, предлагаю перевод сентябрьской задачки от IBM (или прочтите оригинал):

Невозможно на протяжении шести часов так рассаживать по трём стульям трёх человек (Аню, Витю и Сашу), чтобы они пересаживались после каждого часа, причём ни разу не повторили конфигурацию, а также никто два раза подряд не сидел на одном и том же стуле. Рассмотрим "почти" решение:
A B C A B C
B C A C A B
C A B B C A

Единственное нарушение здесь — это "B B" в средней части третей строки.

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

Дополнение от 29 августа: Нарушения считаются по всем четырём участникам отдельно, поэтому при смене ABCD-ABDC будет зафиксировано два нарушения. Также сохранение своей позиции на протяжении трёх часов подряд считается как три нарушения (t vs t+1; t+1 vs t+2 and t vs t+2).


Если вам интересны подобные задачки, то поделитесь, пожалуйста, в комментариях ответами на следующие вопросы:
1) Придумали ли вы решение первой задачи-примера (в которой хоть и нельзя два раза подряд сидеть на одном и том же стуле, но разрешено возвращаться на то место, где был в позапрошлый раз) для четырёх участников и 24 часов с нулевым количеством нарушений?
2) Нашли ли вы решение основной задачи для троих участников и шести часов?
3) Какие эвристики обнаружили, пока решали (1) и (2)? Помогло ли это лучше понять основную задачу?

Хорошей недели и интересных задачек!

9 комментариев:

  1. Анонимный30.08.2016, 19:01

    Разве первое возможно? На 22 часа легко сделать, а дальше не могу.

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

      Удалить
    2. Анонимный15.09.2016, 10:44

      BABABABABACBCDCDCDCDADCD
      ACDCABCDCDADABDABABCBCDB
      DBADCDABDCBCDABCABDACBAC
      CDCBDCDCABDABCABDCABDABA

      Удалить
  2. Анонимный30.08.2016, 23:12

    Что-то я вообще не понял нотацию. По ссылке IBM - не открылось.

    ОтветитьУдалить
    Ответы
    1. Вертикальные столбцы - конфигурации. Соответственно, по горизонтали идут часы.
      Странно, у меня ссылка везде открывалась.

      Удалить
  3. Анонимный31.08.2016, 07:17

    Правильная ссылка: http://researchweb.watson.ibm.com/haifa/ponderthis/challenges/September2016.html

    ОтветитьУдалить
    Ответы
    1. Хорошо, я поменял https на http. Но пока не понимаю, почему у Вас с https не открывалось. Хитрые настройки безопасности?

      Удалить
  4. Анонимный04.10.2016, 15:07

    А решение-то простое: http://researchweb.watson.ibm.com/haifa/ponderthis/solutions/September2016.html

    CBACBADBCDABDCADBCDABDCA
    BACDABCDABDCADBCDABDCABC
    DCBADCBADCBACBDACBACDBAD
    ADDBCDACBACDBACBADCBACDB

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний