Треугольники в n-мерном кубе.

[bot]

Эту задачу сочинил экспромтом, когда читал спецкурс в ФМШ по комбинаторике, будучи студентом или в возрасте аспиранта. Решения в тот момент у меня не было (только идея), а через неделю в случае облома с реализацией идеи мог получиться конфуз. На такие экспромты способны излишне уверенные в себе, начинающие преподы. Впрочем и позже я, бывало, стимулировал себя подобными экспромтами.

Maxal её знает - мог бы показать, где лежит его решение, но воздержусь.

Задача. Найти число число неконгруентных треугольников, вершины которых лежат в вершинах n-мерного куба.

[Антипка]

Задача нетривиальная, размышлял над задачей минут 5 - больше некогда. Очевидно, что число различных треугольников, вершины которых лежат в вершинах n-мерного куба, но не лежат в вершинах кубов меньшей размерности, есть число способов представить число 2n в виде суммы трех чисел из диапазона от 1 до n. Будет время - подумаю дальше.

bot писал(а):

Maxal её знает - мог бы показать, где лежит его решение, но воздержусь

Не просто знает, а вошел в анналы как автор "Additional comments" Собственно, задачка известна издавна и найти ее решение в интернете не представляет непреодолимой сложности.

Добавлено.
Смог выделить задаче несколько 5-минутных квантов своего внимания, вот что за это время придумал:

Развитие вышеизложенной идеи приводит к следующему: рассмотрим следующую таблицу, i-тая строка которой содержит $\left\lfloor{\frac{i}{2}}\right\rfloor+1$ убывающе-последовательных натуральных чисел начиная с 2i.

1: 2
2: 4 3
3: 6 5
4: 8 7 6
5: 10 9 8
6: 12 11 10 9
7: 14 13 12 11
8: 16 15 14 13 12
9: 18 17 16 15 14
.....
Смысл таблицы таков: число искомых треугольников, вершины которых принадлежат n-мерному кубу и не принадлежат кубам меньших размерностей, есть число элементов в этой таблице, не превосходящих n, обозначим это число через b(n). Обозначив тогда искомую величину через a(n), получаем очевидное:

$a(n)=\sum\limits_{i=1}^n{b(i)}$

Осталось получить формулу.
Продолжение следует...

[maxal]

Антипка писал(а):

bot писал(а):

Maxal её знает - мог бы показать, где лежит его решение, но воздержусь

Не просто знает, а вошел в анналы как автор "Additional comments"

Это в OEIS. А bot имел в виду подробное решение на другом форуме. От ссылок пока воздержусь.

[bot]

Что такое OEIS, я не знаю.
Скорее всего открыл велосипед - очень уж классически выглядит, а было это в конце ХХ-х или в самом начале YY-х. До интернета было ещё далековато.

Поправка:

Цитата:

Что такое OEIS, я не знаю.

Нет, теперь уже знаю.

[worm2]

Антипка писал(а):

Очевидно, что число различных треугольников, вершины которых лежат в вершинах n-мерного куба, но не лежат в вершинах кубов меньшей размерности, есть число способов представить число 2n в виде суммы трех чисел из диапазона от 1 до n.

Антипка писал(а):

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

Если бы мне только удалось понять эти утверждения, я бы смог понять, как решать всю задачу.

Антипка писал(а):

Осталось получить формулу.

Это как раз самое простое, только муторное. Если считать по столбцам, то становится очевидной формула

$$b(n)=\left\lfloor\frac{n}{2} \right\rfloor + \left\lfloor\frac{n-1}{2} \right\rfloor + \left\lfloor\frac{n-4}{2} \right\rfloor + \dots + \left\lfloor\frac{n-(3k+1)}{2}\right\rfloor$$

.
Суммирование ведётся, пока последний член не достигнет 2 или 1.
Отсюда легко (только долго ) получается:
$b(6k) = 3k^2+3k$;
$b(6k+1) = 3k^2+4k$;
$b(6k+2) = 3k^2+5k+1$;
$b(6k+3) = 3k^2+6k+2$;
$b(6k+4) = 3k^2+7k+3$;
$b(6k+5) = 3k^2+8k+4$.

Поднапрягшись ещё немного, получаем окончательно:
$a(6k) = (12k^3+21k^2-k)/2$;
$a(6k+1) = (12k^3+27k^2+7k)/2$;
$a(6k+2) = (12k^3+33k^2+17k+2)/2$;
$a(6k+3) = (12k^3+39k^2+29k+6)/2$;
$a(6k+4) = (12k^3+45k^2+43k+12)/2$;
$a(6k+5) = (12k^3+51k^2+59k+20)/2$.

[Антипка]

worm2 писал(а):

Если бы мне только удалось понять эти утверждения, я бы смог понять, как решать всю задачу.

Хотел доделать сегодня, но - увы. У нас сегодня корпоративный праздник, ну и мы тренируем печень к нему с самого утра, празднуем, короче. Так что твои выкладки смогу понять, наверное, не раньше понедельника. Но свои объяснить могу в любом состоянии. Я знаю формулу правильного ответа (он опубликован в OEIS), но пока не знаю решения, а сейчас даже не в состоянии проверить, соответствует ли твой ответ тому, что там приведено. Сам проверь. Зайди на сайт OEIS и ищи последовательность по первым 6-7 членам.

Итак, позиция первая. Введем для вершин нашего кубе следующую метрику: расстоянием сежду двумя вершинами назовем минимальное количество ребер в цепи, соединяющей обе вершины. Если рассмотреть весь треугольник, вершины которого принадлежат множеству вершин n-мерного куба но не принадлежат множеству вершин кубов меньшей размерности, то тогда суммарная длина его сторон в нашей метрике будет равна 2n. действительно, при переходе по циклу, образуемому сторонами треугольника, каждая из размерностей куба должна быть "задействована", то есть мы должны пройти ровно два ребра, соответствующих этой размерности. Для нашей метрики признак конгруэнтности треугольников по трем сторонам остается в силе. Да, в нашей метрике расстояние между двумя различными вершинами куба не превышает его размерности и не меньше 1. Таким образом, мы показали, что искомое число треугольников есть сумма по всем $i\le n$ числа способов представления числа 2i в виде суммы трех слагаемых из диапазона от 1 до i включительно.

Теперь пояснение по поводу таблицы. Рассмотрим число способов представления числа 2n в виде суммы трех чисел, при условии, что наименьшее из чисел равно j. Приведем несколько первых членов, и для каждого способа запишем условие его применимости, а именно, что второе слагаемое в выражении не меньше первого:

j=1: 1 + (n-1) + n,                  n>=2
j=2: 2 + (n-2) + n,                   n>=4            
       2 + (n-1) + (n-1),             n>=3
j=3: 3 + (n-3) + n,                   n>=6
       3 + (n-2) + (n-1),             n>=5
j=4: 4 + (n-4) + n,                   n>=8
       4 + (n-3) + (n-1),             n>=7
       4 + (n-2) + (n-2),             n>=6

............................................
j: j + (n-j) + n, n>=2j
.......................................
$j+(n-\left\lceil{\frac{j}{2}}\right\rceil)+(n-\left\lfloor{\frac{j}{2}} \right\rfloor)$, $n\ge j+\left\lceil{&\frac{j}{2}}\right\rceil$
Таким образом, каждая j-тая строка таблицы соответствует способам представления числа 2n в виде суммы трех чисел из диапазона от 1 до n с наименьшим из трех чисел, равным j, а каждый элемент этой строки означает n, начиная с которого он применим. Таким образом, очевидно, искомое число представлений (b(n)) есть не что иное, как число элементов в таблице, не первышающих n.

[worm2]

Да, идея замечательная. Я бы до такой, наверное, не додумался.
Решение OEIS посмотрел. Проверил два варианта из шести --- совпадает. Остальные уже лень проверять. Ваше решение правильное, мои вычисления тоже. Значит, или остальные варианты тоже совпадают, или в OEIS ошибка

[maxal]

Мое решение приведено тут:
http://www.nsu.ru/phorum/read.php?f=29&i=1478&t=1394

[bot]

worm2 писал(а):

Проверил два варианта из шести --- совпадает.

Остальные четыре - тоже.
P.S. Первый раз попробовал OEIS - нашёл последовательность: A034198.
Только по ссылкам что-то ничего не обнаружил - ни формулы ни подробностей.
Надо бы на досуге заняться освоением этой шняги.

[Антипка]

Хотя, собственно, решение уже опубликовано и не одно...

Рассматривать отдельные варианты размерности куба по модулю 6 и затем обобщать их, как сделали maxal и warm2 в своих выкладках, я бы не смог, уж больно муторно, не в жисть бы не догадался. Вместо этого я бы попытался сделать так:

Для начала посмотрим, сколько раз число i встречается в моей таблице. Обозначим эту величину через N(i). Очевидно, что

$N(i)=\left\lfloor{\frac{i}{6}}\right\rfloor+1-d(i)$, где
$d(i)=\left\{ \begin{array}{l} 1,i \equiv 1(\bmod 6) \\ 0,i \ne 1(\bmod 6) \\ \end{array} \right.$

Теперь посмотрим, сколько раз число i учитывается при вычислении a(n). Очевидно, что оно "входит" в b(i), b(i+1), ..., b(i), т.е. учитывается n+1-i раз. Теперь мы можем записать выражение непосредственно для искомой величины:

$a(n)=(n-1)N(2)+(n-2)N(3)+...+N(n)=\sum\limits_{i=2}^n{(n+1-i)N(i)}$

С учетом того, что (формально) N(1)=0, можно перейти к "стандартным" пределам суммирования:

$a(n)=\sum\limits_{i=1}^n{(n+1-i)N(i)}$.

Подставляя туда выражение для N(n) и учитывая, что пресловутая "поправка" d(i) "вычитает" из N по единице для чисел, сравнимых с 1 по модулю 6, получаем искомый результат в виде выражения с суммированием:

$a(n)=\sum\limits_{i=1}^n{(n+1-i)(\left\lfloor{\frac{i}{6}}\right\rfloor+1)}-\sum\limits_{k=0}^{\left\lfloor{\frac{n}{6}}\right\rfloor}{(n-6k)}$

Добавлено 26.12.06
Собственно, все компоненты этого выражения вычисляются достаточно легко в общем виде:

$\begin{array}{l} \sum\limits_{i = 1}^n {(\left\lfloor {\frac{i}{6}} \right\rfloor + 1) = } \sum\limits_{i = 0}^n {(\left\lfloor {\frac{i}{6}} \right\rfloor + 1) - 1 = } 6 \cdot 1 + 6 \cdot 2 + ... + 6 \cdot \left\lfloor {\frac{n}{6}} \right\rfloor + (n + 1 - 6\left\lfloor {\frac{n}{6}} \right\rfloor )(\left\lfloor {\frac{n}{6}} \right\rfloor + 1) - 1 = \\ = 6\sum\limits_{i = 1}^{\left\lfloor {\frac{n}{6}} \right\rfloor } {i + (n + 1 - 6\left\lfloor {\frac{n}{6}} \right\rfloor )(\left\lfloor {\frac{n}{6}} \right\rfloor + 1) - 1 = } (\left\lfloor {\frac{n}{6}} \right\rfloor + 1)(n + 1 - 3\left\lfloor {\frac{n}{6}} \right\rfloor ) - 1. \\ \end{array}$

$\begin{array}{l} \sum\limits_{i = 1}^n {i(\left\lfloor {\frac{i}{6}} \right\rfloor + 1)} = (\left\lfloor {\frac{n}{6}} \right\rfloor + 1)\sum\limits_{i = 1}^n i - \sum\limits_{k = 1}^{\left\lfloor {\frac{n}{6}} \right\rfloor } {\sum\limits_{i = 1}^{6k - 1} i } = \\ = \frac{{n(n + 1)}}{2}(\left\lfloor {\frac{n}{6}} \right\rfloor + 1) - \sum\limits_{k = 1}^{\left\lfloor {\frac{n}{6}} \right\rfloor } {3k(6k - 1) = } (\left\lfloor {\frac{n}{6}} \right\rfloor + 1)(\frac{{n(n + 1)}}{2} - 6\left\lfloor {\frac{n}{6}} \right\rfloor ^2 - \frac{3}{2}{\left\lfloor {\frac{n}{6}} \right\rfloor}). \\ \end{array}$

$\sum\limits_{k = 0}^{\left\lfloor {\frac{n}{6}} \right\rfloor } {(n - 6k) = n} (\left\lfloor {\frac{n}{6}} \right\rfloor + 1) - 6\sum\limits_{k = 0}^{\left\lfloor {\frac{n}{6}} \right\rfloor } k = (\left\lfloor {\frac{n}{6}} \right\rfloor + 1)(n - 3\left\lfloor {\frac{n}{6}} \right\rfloor ).$

В итоге получаем следующее выражение:
$a(n) = (\left\lfloor {\frac{n}{6}} \right\rfloor + 1)(\frac{{n(n + 1)}}{2} + 1 + \left\lfloor {\frac{n}{6}} \right\rfloor (6\left\lfloor {\frac{n}{6}} \right\rfloor - 3n + \frac{3}{2})) - (n + 1).$

То, что это результат правильный, можно убедиться с помощью вот этой программы:

#include <stdio.h>

long f(long n);

int main(int argc, char *argv[])
{
  if (argc == 2)
  {
    int i; long n=atol(argv[1]);
    for(i=2; i<=n; i++) printf("%ld: %ld\n", i, f(i)); 
  }
}
long f(long n)
{
  long n6=n/6;
  return n<2 ?  0 : (n6+1)*(n*(n+1)/2 + 1 + n6*(6*n6-3*n)) + n6*(n6+1)/2*3 - (n+1);
}

Остался сущий пустячок - преобразовать формулу к "каноническому" виду.