Раскраска поверхности кубика
От: kfmn Россия  
Дата: 31.03.17 10:56
Оценка: 5 (1)
Дочка с олимпиады принесла:

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

Ответ находится быстро, а вот чтобы доказать, почему он максимальный — пришлось поломать голову.
Возможно, кто-то из вас найдет более простое доказательство.
Re: Раскраска поверхности кубика
От: Кодт Россия  
Дата: 31.03.17 14:10
Оценка:
Здравствуйте, kfmn, Вы писали:

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

22

K>Ответ находится быстро, а вот чтобы доказать, почему он максимальный — пришлось поломать голову.
K>Возможно, кто-то из вас найдет более простое доказательство.

Доказал брутфорсом
Всего-то пришлось перебрать чуть меньше 62 миллионов вариантов и получить 48 разных решений (без оглядки на повороты-отражения).
Перекуём баги на фичи!
Re[2]: Раскраска поверхности кубика
От: Кодт Россия  
Дата: 31.03.17 14:21
Оценка:
К>Всего-то пришлось перебрать чуть меньше 62 миллионов вариантов и получить 48 разных решений (без оглядки на повороты-отражения).

Ниже — полный список, сгруппированный по количеству чёрных клеток на сторонах.
Разные группы — очевидно, разные классы решений. И в одной группе обнаружил два разных класса.

6 решений (3, 3, 3, 3, 5, 5)
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|@..|@..|@..|@..|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+

  остальные 5 
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|..@|..@|..@|..@|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |...|                               
+---+---+---+---+                       
|@.@|.@.|@.@|...|                       
|.@.|@.@|.@.|@.@|                       
|@.@|...|@.@|.@.|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |...|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@..|                               
    |.@.|                               
+---+---+---+---+                       
|...|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|...|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |..@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |..@|                               
    |.@.|                               
+---+---+---+---+                       
|.@.|@.@|...|@.@|                       
|@.@|.@.|@.@|.@.|                       
|...|@.@|.@.|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |@..|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |...|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|@.@|...|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|...|                       
+---+---+---+---+                       
    |...|                               
    |@.@|                               
    |.@.|                               
    +---+

6 решений (2, 2, 4, 4, 5, 5) 
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|@.@|...|@.@|...|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+

  остальные 5 
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|...|@.@|...|@.@|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|@.@|...|@.@|...|                       
|.@.|@.@|.@.|@.@|                       
|@.@|...|@.@|...|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|...|@.@|...|@.@|                       
|@.@|.@.|@.@|.@.|                       
|...|@.@|...|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |...|                               
    |.@.|                               
+---+---+---+---+                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |...|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |...|                               
    |@.@|                               
    |...|                               
+---+---+---+---+                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
+---+---+---+---+                       
    |...|                               
    |@.@|                               
    |...|                               
    +---+

36 решений (2, 3, 3, 4, 5, 5)
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|@.@|..@|..@|...|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               

    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|@.@|..@|...|@..|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+

  остальные 34 
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|@.@|..@|...|@..|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|@.@|...|@..|@..|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|@..|@.@|..@|...|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|@..|@.@|...|@..|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|@..|@..|@.@|...|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|..@|..@|...|@.@|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|..@|...|@.@|..@|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|..@|...|@..|@.@|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|...|@.@|..@|..@|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|...|@..|@.@|..@|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |@.@|                               
    |.@.|                               
    |@.@|                               
+---+---+---+---+                       
|.@.|.@.|.@.|.@.|                       
|...|@..|@..|@.@|                       
|.@.|.@.|.@.|.@.|                       
+---+---+---+---+                       
    |@.@|                               
    |.@.|                               
    |@.@|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|@.@|...|@.@|...|                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
+---+---+---+---+                       
    |...|                               
    |@.@|                               
    |...|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|@.@|...|@.@|...|                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|...|                       
+---+---+---+---+                       
    |...|                               
    |@.@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|@.@|...|@.@|...|                       
|.@.|@.@|.@.|@.@|                       
|@.@|...|@.@|.@.|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |...|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|...|@.@|...|@.@|                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |...|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|...|@.@|...|@.@|                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|...|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |..@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|...|@.@|...|@.@|                       
|@.@|.@.|@.@|.@.|                       
|...|@.@|.@.|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |@..|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |...|                               
+---+---+---+---+                       
|@.@|.@.|@.@|...|                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
+---+---+---+---+                       
    |...|                               
    |@.@|                               
    |...|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |...|                               
+---+---+---+---+                       
|@.@|.@.|@.@|...|                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|...|                       
+---+---+---+---+                       
    |...|                               
    |@.@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@.@|                               
    |...|                               
+---+---+---+---+                       
|@.@|.@.|@.@|...|                       
|.@.|@.@|.@.|@.@|                       
|@.@|...|@.@|...|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@..|                               
    |.@.|                               
+---+---+---+---+                       
|...|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |...|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@..|                               
    |.@.|                               
+---+---+---+---+                       
|...|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
|...|@.@|.@.|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |@..|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |@..|                               
    |.@.|                               
+---+---+---+---+                       
|...|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
|...|@.@|...|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |..@|                               
    |.@.|                               
+---+---+---+---+                       
|.@.|@.@|...|@.@|                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |...|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |..@|                               
    |.@.|                               
+---+---+---+---+                       
|.@.|@.@|...|@.@|                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|...|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |..@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |..@|                               
    |.@.|                               
+---+---+---+---+                       
|.@.|@.@|...|@.@|                       
|@.@|.@.|@.@|.@.|                       
|...|@.@|...|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |...|                               
    |.@.|                               
+---+---+---+---+                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|...|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |..@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |...|                               
    |.@.|                               
+---+---+---+---+                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
|...|@.@|.@.|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |@..|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |.@.|                               
    |...|                               
    |.@.|                               
+---+---+---+---+                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
|...|@.@|...|@.@|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |...|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|@.@|...|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|.@.|                       
+---+---+---+---+                       
    |...|                               
    |@.@|                               
    |...|                               
    +---+                               
                                        
    +---+                               
    |...|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|@.@|...|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
|@.@|...|@.@|.@.|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |...|                               
    +---+                               
                                        
    +---+                               
    |...|                               
    |@.@|                               
    |.@.|                               
+---+---+---+---+                       
|@.@|...|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
|@.@|...|@.@|...|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |...|                               
    |@.@|                               
    |...|                               
+---+---+---+---+                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
|@.@|.@.|@.@|...|                       
+---+---+---+---+                       
    |...|                               
    |@.@|                               
    |.@.|                               
    +---+                               
                                        
    +---+                               
    |...|                               
    |@.@|                               
    |...|                               
+---+---+---+---+                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
|@.@|...|@.@|.@.|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |...|                               
    +---+                               
                                        
    +---+                               
    |...|                               
    |@.@|                               
    |...|                               
+---+---+---+---+                       
|@.@|.@.|@.@|.@.|                       
|.@.|@.@|.@.|@.@|                       
|@.@|...|@.@|...|                       
+---+---+---+---+                       
    |.@.|                               
    |@.@|                               
    |.@.|                               
    +---+
Перекуём баги на фичи!
Отредактировано 31.03.2017 14:25 Кодт . Предыдущая версия . Еще …
Отредактировано 31.03.2017 14:24 Кодт . Предыдущая версия .
Re[2]: Раскраска поверхности кубика
От: kfmn Россия  
Дата: 31.03.17 14:58
Оценка:
Здравствуйте, Кодт, Вы писали:

K>>Возможно, кто-то из вас найдет более простое доказательство.

К>Доказал брутфорсом

Я еще думал, правильно ли сюда постить просто задачу на подумать...
А оказалось, что это-таки этюд для программистов

К>Всего-то пришлось перебрать чуть меньше 62 миллионов вариантов и получить 48 разных решений (без оглядки на повороты-отражения).
Re[3]: Раскраска поверхности кубика
От: Кодт Россия  
Дата: 31.03.17 15:05
Оценка:
Здравствуйте, kfmn, Вы писали:

K>Я еще думал, правильно ли сюда постить просто задачу на подумать...
K>А оказалось, что это-таки этюд для программистов

Ну, когда стало понятно, что могут быть разные решения, — то, естественно, встал вопрос: как получить их все.

А заниматься преждевременным учётом симметрии мне было лень. Очень быстро увидел, что скорости тупого перебора на питоне достаточно, подождал пять минут и распечатал.
Перекуём баги на фичи!
Re[2]: Раскраска поверхности кубика
От: kfmn Россия  
Дата: 31.03.17 17:32
Оценка: 61 (7)
Здравствуйте, Кодт, Вы писали:

K>>Какое максимальное число клеток можно закрасить?

К>22

  Под катом мое обоснование, почему нельзя больше.

Выделим на кубике 3 группы клеток (см. рисунок):
    24 красные — в вершинах куба
    18 зеленых — 2 полосы по 9 клеток
    12 синих — в серединах ребер, не попавших в зеленые полосы
На каждой вершине может быть закрашена только 1 красная клетка из трех — итого максимум 8;
В каждой зеленой полосе любая клетка соседствует по стороне с двумя другими, поэтому из 9 клеток удастся закрасить еще максимум 4 — итого еще максимум 8;
На каждой оставшейся середине ребра можно закрасить только одну клетку из двух синих — итого еще максимум 6.
Re: Раскраска поверхности тессеракта
От: Alexander G Украина  
Дата: 05.08.18 14:09
Оценка: 5 (1)
Здравствуйте, kfmn, Вы писали:

K>Дочка с олимпиады принесла:

K>Есть белый кубик со стороной 3 клетки.

Тут коллега предложила модификацию задачки, где у нас не куб, а тессеракт, но мы всё ещё красим клетки-квадраты...
Русский военный корабль идёт ко дну!
Re[2]: Раскраска поверхности тессеракта
От: Кодт Россия  
Дата: 08.08.18 20:14
Оценка:
Здравствуйте, Alexander G, Вы писали:

AG>Тут коллега предложила модификацию задачки, где у нас не куб, а тессеракт, но мы всё ещё красим клетки-квадраты...

У куба центральные и боковые клетки сторон граничат с соседями в шахматном порядке. То есть, сосед соседа — не мой сосед.
У тессеракта же все клетки — "угловые".

Всего 648 клеток.
Зарядил перебор, — пока что нашёл решение на 155 клеток... улучшить ещё не смог.

UPD. Уже есть 156.
Перекуём баги на фичи!
Отредактировано 09.08.2018 0:09 Кодт . Предыдущая версия .
Re[3]: Раскраска поверхности тессеракта
От: Alexander G Украина  
Дата: 09.08.18 05:51
Оценка:
Здравствуйте, Кодт, Вы писали:


К>У куба центральные и боковые клетки сторон граничат с соседями в шахматном порядке. То есть, сосед соседа — не мой сосед.
К>У тессеракта же все клетки — "угловые".

К>Всего 648 клеток.

Что-то не то, я совсем не понимаю, каким образом 648.

Мы о плоских клетках на плоских гранях тессеракта, так?
У него 8 кубов, у каждого куба 6 граней, итого было бы 48 плоских граней, но каждая грань — между двумя кубами, поэтому их 24 (сходится с инфой из Википедии).

Разобьём каждую на 9 клеток, итого 216 клеток.

Теперь, каждое ребро (которое двумерный отрезок) — стык трёх граней (по три клетки с каждой, итого 9 клеток касаются ребра). Поэтому закрасить можно меньше, чем если бы это были независимые кубы.

Коллега смогла закрасить некоторое количество. Пока без доказательства, что это решение оптимально.

  Её решение
76 клеток

(Я пока не пытался решать)
Русский военный корабль идёт ко дну!
Отредактировано 09.08.2018 5:55 Alexander G . Предыдущая версия .
Re[4]: Раскраска поверхности тессеракта
От: Кодт Россия  
Дата: 09.08.18 09:12
Оценка:
Здравствуйте, Alexander G, Вы писали:

К>>Всего 648 клеток.
AG>Что-то не то, я совсем не понимаю, каким образом 648.

AG>Мы о плоских клетках на плоских гранях тессеракта, так?
AG>У него 8 кубов, у каждого куба 6 граней, итого было бы 48 плоских граней, но каждая грань — между двумя кубами, поэтому их 24 (сходится с инфой из Википедии).

Так! Интересно, чего же я там нагенерил... Видимо, посчитал все внутренние клетки кубиков.
Перекуём баги на фичи!
Re: Раскраска поверхности кубика
От: scf  
Дата: 09.08.18 11:54
Оценка:
Здравствуйте, kfmn, Вы писали:

K>Возможно, кто-то из вас найдет более простое доказательство.

Задача о раскраске вершин графа?
Re[4]: Раскраска поверхности тессеракта
От: Кодт Россия  
Дата: 10.08.18 10:46
Оценка: 5 (1)
Здравствуйте, Alexander G, Вы писали:

AG>Коллега смогла закрасить некоторое количество. Пока без доказательства, что это решение оптимально.

AG>Её решение
AG>76 клеток

Случайным перебором нашёл 80.
  координаты клеток 
<0,0,0,0> - <0,0,0,1> - <0,0,1,1> - <0,0,1,0>
<0,0,0,0> - <0,1,0,0> - <1,1,0,0> - <1,0,0,0>
<0,0,0,1> - <0,0,0,2> - <1,0,0,2> - <1,0,0,1>
<0,0,0,2> - <0,0,0,3> - <0,1,0,3> - <0,1,0,2>
<0,0,0,3> - <0,0,1,3> - <1,0,1,3> - <1,0,0,3>
<0,0,1,0> - <0,0,2,0> - <0,1,2,0> - <0,1,1,0>
<0,0,1,1> - <0,0,1,2> - <0,0,2,2> - <0,0,2,1>
<0,0,1,3> - <0,0,2,3> - <0,1,2,3> - <0,1,1,3>
<0,0,2,0> - <0,0,3,0> - <1,0,3,0> - <1,0,2,0>
<0,0,2,2> - <0,0,2,3> - <0,0,3,3> - <0,0,3,2>
<0,0,3,0> - <0,0,3,1> - <0,1,3,1> - <0,1,3,0>
<0,0,3,1> - <0,0,3,2> - <1,0,3,2> - <1,0,3,1>
<0,0,3,3> - <0,1,3,3> - <1,1,3,3> - <1,0,3,3>
<0,1,0,0> - <0,1,1,0> - <0,2,1,0> - <0,2,0,0>
<0,1,0,1> - <0,1,0,2> - <0,2,0,2> - <0,2,0,1>
<0,1,0,3> - <0,1,1,3> - <0,2,1,3> - <0,2,0,3>
<0,1,2,0> - <0,1,3,0> - <0,2,3,0> - <0,2,2,0>
<0,1,2,3> - <0,1,3,3> - <0,2,3,3> - <0,2,2,3>
<0,1,3,1> - <0,1,3,2> - <0,2,3,2> - <0,2,3,1>
<0,2,0,0> - <0,3,0,0> - <1,3,0,0> - <1,2,0,0>
<0,2,0,2> - <0,2,0,3> - <0,3,0,3> - <0,3,0,2>
<0,2,1,0> - <0,2,2,0> - <0,3,2,0> - <0,3,1,0>
<0,2,1,3> - <0,2,2,3> - <0,3,2,3> - <0,3,1,3>
<0,2,3,0> - <0,2,3,1> - <0,3,3,1> - <0,3,3,0>
<0,2,3,3> - <0,3,3,3> - <1,3,3,3> - <1,2,3,3>
<0,3,0,0> - <0,3,0,1> - <0,3,1,1> - <0,3,1,0>
<0,3,0,1> - <0,3,0,2> - <1,3,0,2> - <1,3,0,1>
<0,3,0,3> - <0,3,1,3> - <1,3,1,3> - <1,3,0,3>
<0,3,1,1> - <0,3,1,2> - <0,3,2,2> - <0,3,2,1>
<0,3,2,0> - <0,3,3,0> - <1,3,3,0> - <1,3,2,0>
<0,3,2,2> - <0,3,2,3> - <0,3,3,3> - <0,3,3,2>
<0,3,3,1> - <0,3,3,2> - <1,3,3,2> - <1,3,3,1>
<1,0,0,0> - <1,0,0,1> - <2,0,0,1> - <2,0,0,0>
<1,0,0,2> - <1,0,0,3> - <2,0,0,3> - <2,0,0,2>
<1,0,1,0> - <1,0,2,0> - <2,0,2,0> - <2,0,1,0>
<1,0,1,3> - <1,0,2,3> - <2,0,2,3> - <2,0,1,3>
<1,0,3,0> - <1,0,3,1> - <2,0,3,1> - <2,0,3,0>
<1,0,3,2> - <1,0,3,3> - <2,0,3,3> - <2,0,3,2>
<1,1,0,0> - <1,2,0,0> - <2,2,0,0> - <2,1,0,0>
<1,1,0,3> - <1,2,0,3> - <2,2,0,3> - <2,1,0,3>
<1,1,3,0> - <1,2,3,0> - <2,2,3,0> - <2,1,3,0>
<1,1,3,3> - <1,2,3,3> - <2,2,3,3> - <2,1,3,3>
<1,3,0,0> - <1,3,0,1> - <2,3,0,1> - <2,3,0,0>
<1,3,0,2> - <1,3,0,3> - <2,3,0,3> - <2,3,0,2>
<1,3,1,0> - <1,3,2,0> - <2,3,2,0> - <2,3,1,0>
<1,3,1,3> - <1,3,2,3> - <2,3,2,3> - <2,3,1,3>
<1,3,3,0> - <1,3,3,1> - <2,3,3,1> - <2,3,3,0>
<1,3,3,2> - <1,3,3,3> - <2,3,3,3> - <2,3,3,2>
<2,0,0,0> - <2,1,0,0> - <3,1,0,0> - <3,0,0,0>
<2,0,0,1> - <2,0,0,2> - <3,0,0,2> - <3,0,0,1>
<2,0,0,3> - <2,1,0,3> - <3,1,0,3> - <3,0,0,3>
<2,0,3,0> - <2,1,3,0> - <3,1,3,0> - <3,0,3,0>
<2,0,3,1> - <2,0,3,2> - <3,0,3,2> - <3,0,3,1>
<2,0,3,3> - <2,1,3,3> - <3,1,3,3> - <3,0,3,3>
<2,2,0,3> - <2,3,0,3> - <3,3,0,3> - <3,2,0,3>
<2,2,3,0> - <2,3,3,0> - <3,3,3,0> - <3,2,3,0>
<2,2,3,3> - <2,3,3,3> - <3,3,3,3> - <3,2,3,3>
<2,3,0,0> - <2,3,1,0> - <3,3,1,0> - <3,3,0,0>
<2,3,0,1> - <2,3,0,2> - <3,3,0,2> - <3,3,0,1>
<2,3,3,1> - <2,3,3,2> - <3,3,3,2> - <3,3,3,1>
<3,0,0,0> - <3,0,0,1> - <3,0,1,1> - <3,0,1,0>
<3,0,0,2> - <3,0,0,3> - <3,0,1,3> - <3,0,1,2>
<3,0,1,0> - <3,0,2,0> - <3,1,2,0> - <3,1,1,0>
<3,0,1,1> - <3,0,1,2> - <3,0,2,2> - <3,0,2,1>
<3,0,1,3> - <3,0,2,3> - <3,1,2,3> - <3,1,1,3>
<3,0,2,0> - <3,0,2,1> - <3,0,3,1> - <3,0,3,0>
<3,0,2,2> - <3,0,2,3> - <3,0,3,3> - <3,0,3,2>
<3,1,0,0> - <3,1,1,0> - <3,2,1,0> - <3,2,0,0>
<3,1,0,1> - <3,1,0,2> - <3,2,0,2> - <3,2,0,1>
<3,1,0,3> - <3,1,1,3> - <3,2,1,3> - <3,2,0,3>
<3,1,2,0> - <3,1,3,0> - <3,2,3,0> - <3,2,2,0>
<3,1,2,3> - <3,1,3,3> - <3,2,3,3> - <3,2,2,3>
<3,1,3,1> - <3,1,3,2> - <3,2,3,2> - <3,2,3,1>
<3,2,0,0> - <3,2,0,1> - <3,3,0,1> - <3,3,0,0>
<3,2,1,0> - <3,2,2,0> - <3,3,2,0> - <3,3,1,0>
<3,2,1,3> - <3,2,2,3> - <3,3,2,3> - <3,3,1,3>
<3,3,0,2> - <3,3,0,3> - <3,3,1,3> - <3,3,1,2>
<3,3,1,1> - <3,3,1,2> - <3,3,2,2> - <3,3,2,1>
<3,3,2,0> - <3,3,2,1> - <3,3,3,1> - <3,3,3,0>
<3,3,2,2> - <3,3,2,3> - <3,3,3,3> - <3,3,3,2>
Перекуём баги на фичи!
Re[2]: Раскраска поверхности тессеракта
От: Кодт Россия  
Дата: 10.08.18 19:58
Оценка: :)
Здравствуйте, Alexander G, Вы писали:

AG>Тут коллега предложила модификацию задачки, где у нас не куб, а тессеракт, но мы всё ещё красим клетки-квадраты...

Наговнокодил генетический алгоритм, он на тессеракте смог родить только решения по 80 клеток. Похоже, что это предел.

На 5-мерном кубе — за 500 поколений он добирается до решения с 200 плитками... или не добирается.
  говнокод, я предупреждал 
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import random
import itertools

DIMS = 5
SECTIONS = 3  # split the hypercube's side into N parts

POOLSIZE = 10
GENERATIONS = 500

class Method:
    RETRY = 1
    CROSS = 2
METHOD = Method.CROSS

# data types: point, line, tile

class P(tuple):
    ''' point '''
    def __new__(cls,*coords):
        assert len(coords) == DIMS
        return tuple.__new__(cls,coords)
    def __repr__(self):
        return '<%s>' % ','.join(map(str,self))
    def __add__(self,p):
        return P(*(x1+x2 for x1,x2 in zip(self,p)))
    def __sub__(self,p):
        return P(*(x1-x2 for x1,x2 in zip(self,p)))
    
class L(tuple):
    ''' line '''
    def __new__(cls,p1,p2):
        return tuple.__new__(cls,sorted((p1,p2)))
    def __repr__(self):
        return '-'.join(map(str,self))

class T(tuple):
    ''' tile '''
    def __new__(cls,p1,p2,p3,p4):
        return tuple.__new__(cls,(p1,p2,p3,p4))
    def __repr__(self):
        return ' - '.join(map(str, self))
    def sides(self):
        p1,p2,p3,p4 = self
        return [L(p1,p2),L(p2,p3),L(p3,p4),L(p4,p1)]

# check if a coordinate lays on the side
def x_side(x):
    return x==0 or x==SECTIONS

# points on the 2D surface of the hypercube
points = [
    P(*coords)
    for coords in itertools.product(*[range(SECTIONS+1) for d in range(DIMS)])
    if sum(map(x_side,coords)) >= DIMS-2
]

print('ALL POINTS:', len(points))

# offsets of 3 other corners of a tile: +1 by 2 given dimensions
def make_offsets(i,j):
    assert 0 <= i < j < DIMS
    yield P(*[int(k==j) for k in range(DIMS)])
    yield P(*[int(k==i or k==j) for k in range(DIMS)])
    yield P(*[int(k==i) for k in range(DIMS)])

offsets = [
    list(make_offsets(i,j))
    for i in range(DIMS-1) for j in range(i+1, DIMS)
    ]

print('ALL OFFSETS:', len(offsets))

# tiles on the surface of hypercube: all their corners should belong the surface
tiles = [
    T(p,q,r,s)
    for p in points
    for dq,dr,ds in offsets
    for q,r,s in [(p+dq,p+dr,p+ds)]
    if q in points and r in points and s in points
    ]

print('ALL TILES:', len(tiles))

# will identify tiles with their sequential numbers in the list.
N = len(tiles)
Tr = range(N)

# check if two tiles are adjacent
def is_adj(t1,t2):
    return bool(set(t1.sides()) & set(t2.sides()))

# adjacency predicate (all with all)
IsA = {
    (i,j) : i != j and is_adj(ti,tj)
    for i,ti in enumerate(tiles) for j,tj in enumerate(tiles)
    }

# adjacent neighbours
A = { i : {j for j in Tr if IsA[i,j]} for i in Tr }

# improve a candidate to solution (a set of black tiles)
def improve(blacks):
    ideal = set(blacks)

    # delete all conflicting tiles
    for i in blacks:
        ideal -= A[i]
    
    # find all unset tiles (neither blacks nor their neighbours)
    zeros = set(Tr)
    zeros -= blacks
    for i in blacks:
        zeros -= A[i]

    # paint them black in random order
    order = list(zeros)
    random.shuffle(order)
    for i in order:
        if i in zeros:
            ideal.add(i)
            zeros -= A[i]  # exclude neighbours
            if not zeros:
                break

    return frozenset(ideal)

# genetic algorithm: split a solution to two random smaller parts
def split(blacks):
    order = list(blacks)
    random.shuffle(order)
    m = len(order) // 5  # 2/5 and 2/5
    return {frozenset(order[:m*2]), frozenset(order[m*3:])}

# method: split and recombine one set
def retry(b):
    p,q = split(b)
    return improve(p|q)

# method: split and recombine two sets
def cross(b1, b2):
    s1 = split(b1)
    s2 = split(b2)
    return [improve(p|q) for p in s1 for q in s2]

# pool of best solutions
pool = []

def status():
    return [len(p) for p in pool[-10:]]

# initialize the pool
def start():
    global pool
    pool = sorted((frozenset(improve(set())) for t in range(POOLSIZE)), key=len)

# new generation:
def generation():
    global pool

    newpool = set(pool)
    for p in pool:
        if METHOD == Method.RETRY:
            newpool |= {retry(p)}
        else:
            for q in pool:
                newpool |= frozenset(cross(p, q))

    pool = sorted(newpool, key=len)[-POOLSIZE:]

print('GO...')
start()
print(0, status())
def rungens(G=GENERATIONS):
    for t in range(G):
        generation()
        print(t, status())
rungens()
Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.