2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Треугольники в n-мерном кубе.
Сообщение21.12.2006, 11:08 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 
Сообщение21.12.2006, 14:02 


01/12/05
196
Москва
Задача нетривиальная, размышлял над задачей минут 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)}$

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

 Профиль  
                  
 
 
Сообщение21.12.2006, 14:13 
Модератор
Аватара пользователя


11/01/06
5660
Антипка писал(а):
bot писал(а):
Maxal её знает - мог бы показать, где лежит его решение, но воздержусь

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

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

 Профиль  
                  
 
 
Сообщение21.12.2006, 15:41 
Заслуженный участник
Аватара пользователя


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

Поправка:
Цитата:
Что такое OEIS, я не знаю.

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

 Профиль  
                  
 
 
Сообщение22.12.2006, 15:05 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Антипка писал(а):
Очевидно, что число различных треугольников, вершины которых лежат в вершинах 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$.

 Профиль  
                  
 
 
Сообщение22.12.2006, 16:42 


01/12/05
196
Москва
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.

 Профиль  
                  
 
 
Сообщение22.12.2006, 21:02 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение22.12.2006, 22:33 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение24.12.2006, 11:12 
Заслуженный участник
Аватара пользователя


21/12/05
5904
Новосибирск
worm2 писал(а):
Проверил два варианта из шести --- совпадает.
Остальные четыре - тоже. :D
P.S. Первый раз попробовал OEIS - нашёл последовательность: A034198.
Только по ссылкам что-то ничего не обнаружил - ни формулы ни подробностей. :oops:
Надо бы на досуге заняться освоением этой шняги.

 Профиль  
                  
 
 
Сообщение25.12.2006, 09:21 


01/12/05
196
Москва
Хотя, собственно, решение уже опубликовано и не одно...

Рассматривать отдельные варианты размерности куба по модулю 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);
}


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group