Еще геом. задачка (Кубик-II)

[Visitor]

Возьмем банальный трехмерный кубик.
0-мерными гранями будем называть его вершины.
1-мерными гранями будем называть его ребра
2-мерными гранями называть его плоские квадратные грани

Задачка: раскрасить все k-мерные грани в разные цвета, так, чтобы две соседние грани (имеющие общую k-1-мерную сторону, касающиеся друг друга), были покрашены в разный цвет. Сколько нужно красок?

Для трехмерного кубика все просто: вершины (0-грани) можно красить в 1 цвет, т.к., они друг друга не касаются. для ребер (1-грани) надо 3 краски (меньше точно нельзя, т.к., по три ребра сходятся в вершине, больше не надо, легко проверить), для сторон (2-грани) тоже надо три краски.

Теперь задача: сколько надо красок для раскраски k-граней N-мерного кубика?

Сообщение отредактировано: Visitor - 06.11.03, 19:59

[Sazabis]

уж больно задачу о 4 красках напоминает

[Visitor]

Та была на плоскости, даже не на торе Тут веселее

[Sazabis]

я к тому что ее вроде влоб решили

[Visitor]

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

Здесь граф более "регулярный".

[Sazabis]

что то давольно просто получается:

0k = 1 always
1k = N always ( думаю больше не понадобится , так как все симетрично, если углы замалевать, то остальные по инерции сойдутся )

(N-1)k = N always ( чето хорошо начал на бумаге рисовать эти Н-угольники , если правильно рисую, то с прибавлением каждого измерения, N-1 измерение, остается таким же как и до этого рисовал N-1, по отношению к N-2 )

а вот с 2k для 4 мерного пришлось повозиться, но пришел к выводу что все таки будет 4 краски,
а так как они все растут как то пропорционально, то можно сказать что от 2k до (N-1)k, будет N красок.

[Visitor]

С промежуточными посложнее будет... Не N.

И вот еще более общая задачка сразу: k-грани N-мерного куба считаем соседними, если они имеют общую l-мерную сторону (l-грань). 0<l<k<N

Сколько надо красок в етом случае?