Сообщение Re: Еще одна задача про рыцарей от 11.06.2015 9:22
Изменено 11.06.2015 9:44 Кодт
Здравствуйте, baily, Вы писали:
<>
Пока не придумал доказательств, ставлю эксперименты (брутфорсю).
Для N=5 рыцари в первый же день переберут все браслеты (12 штук).
Для N=6 всего браслетов 60, за один день можно перебрать 26 либо 33 браслета (ровно два подмножества).
Для N=7 всего 360, и опять два подмножества — 57 и 302.
Для N=8 всего 2520, и уже 3 подмножества — 120, 1191, 1208.
<>
Пока не придумал доказательств, ставлю эксперименты (брутфорсю).
Для N=5 рыцари в первый же день переберут все браслеты (12 штук).
Для N=6 всего браслетов 60, за один день можно перебрать 26 либо 33 браслета (ровно два подмножества).
Для N=7 всего 360, и опять два подмножества — 57 и 302.
Для N=8 всего 2520, и уже 3 подмножества — 120, 1191, 1208.
Re: Еще одна задача про рыцарей
Здравствуйте, baily, Вы писали:
<>
Пока не придумал доказательств, ставлю эксперименты (брутфорсю).
Для N=5 рыцари во второй же день переберут все браслеты (11 из 12). На третий день браслетов не останется.
Для N=6 всего браслетов 60, за один день можно перебрать 26 либо 33 браслета (ровно два класса).
И т.д.
Очевидно и важно, что из любого начального браслета в классе "все браслеты одного дня" можно достичь любого другого, поскольку рыцарям не запрещено делать перестановки туда-обратно. То есть, это не цепочка, а просто связный неориентированных граф.
На 12 брутфорсилка сломалась — закончилась память (я не особо старался её оптимизировать).
Количество браслетов растёт, очевидно, по экспоненте, а количество классов — как-то очень полого (линейно?)
<>
Пока не придумал доказательств, ставлю эксперименты (брутфорсю).
Для N=5 рыцари во второй же день переберут все браслеты (11 из 12). На третий день браслетов не останется.
Для N=6 всего браслетов 60, за один день можно перебрать 26 либо 33 браслета (ровно два класса).
И т.д.
Очевидно и важно, что из любого начального браслета в классе "все браслеты одного дня" можно достичь любого другого, поскольку рыцарям не запрещено делать перестановки туда-обратно. То есть, это не цепочка, а просто связный неориентированных граф.
N / браслеты / классы / размеры классов
4 3 2 1, 2
5 12 2 1, 11
6 60 3 1, 26, 33
7 360 3 1, 57, 302
8 2520 4 1, 120, 1191, 1208
9 20160 4 1, 247, 4293, 15619
10 181440 5 1, 502, 14608, 78095, 88234
11 1814400 5 1, 1013, 47840, 455192, 1310354
На 12 брутфорсилка сломалась — закончилась память (я не особо старался её оптимизировать).
Количество браслетов растёт, очевидно, по экспоненте, а количество классов — как-то очень полого (линейно?)