6
2

Не так давно мы проводили межвузовскую студенческую олимпиаду. Я придумал для неё одну задачу, которая в итоговый список не вошла, и я хочу предложить её здесь. Решение принимается только с полным доказательством.

Пусть $%n$% -- натуральное число. Рассматриваются все треугольники с целочисленными сторонами, длины каждой из которых не превосходят $%n$%.

а) Сколько имеется таких треугольников для каждого $%n$%?

б) Сколько имеется разносторонних треугольников с тем же свойством?

в) При каком наименьшем значении $%n$% разносторонних треугольников будет больше половины от числа всех?

задан 21 Дек '13 12:32

10|600 символов нужно символов осталось
4

a) Что-то у меня сегодня не получается написать ответ этой задачи. 3 раза уже потеряла текст. По этому пишу без подробных обьяснений . Пусть $%(x;y;z)$% стороны треугольника. Тогда системой $%0< x\le n,0< y\le n, 0< z\le n, x+y>z , x+z>y, y+z>x $% определяется множество всех точек координати которых стороны таких треугольников. Это множество шестиугольник $%LNM_1K_1N_1 $%, Обозначим (G) . Нужно определить число целочисленных точек шестиугольникa $%G.$%

$%G=T-(A\cup B\cup C),$% где $%G-$% куб, а $%A,B,C$% тетраэдры (см. рисунок). Через $%\rho(Q)$% обозначим число целочисленных точек множества $%Q.$%

$%\rho(T)=(n+1)^2.$%

$% \rho(A)=\rho(B)=\rho(C)=1+3+6+...+\frac{(n+1)(n+2)}2=\frac{(n+1)(n+2)(n+3}6.$% Пересечение $%A\cap B$%-это отрезок $%LN,$% Который содержит $%(n+1)$% целочисленных точек. Аналогично для двух других пар тетраэдров. А пересечение всех трех тетраэдров -это точка $%L.$% $%\rho (A\cup B\cup C)= \rho(A)+\rho(B)+\rho(C)-\rho(A\cap B)-\rho(A\cap C)-\rho(C\cap B)+\rho(A\cap B\cup C)=$%

$%=3\cdot \frac{(n+1)(n+2)(n+3}6-3(n+1)+1=\frac{n(n+1)(n+5)+2}2.$% $%\rho(G)=\rho(T)-\rho(A\cup B\cup C)=(n+1)^3-\frac{n(n+1)(n+5)+2}2=\frac{n(n^2+1)}2$%

alt text

Вынуждена написать по частям. Так что продолжение следует.

ссылка

отвечен 22 Дек '13 22:22

изменен 22 Дек '13 22:53

Решение пока не дописано до конца, поэтому я не хотел бы его подробно комментировать, но пока что обращаю внимание, что мы учитываем не тройки длин $%(x,y,z)$%, а сами треугольники, каждый из которых должен учитываться ровно один раз. В этом смысле $%(2;3;4)$% и $%(3;4;2)$% и т.п. -- одно и то же.

P.S. Картинка в самом низу мне в данный момент не видна.

(23 Дек '13 0:24) falcao
10|600 символов нужно символов осталось
3

а) Число способов составить тройки натуральных чисел $%(x,y,z)$%, где $%x\leqslant y\leqslant z\leqslant n$% равно соответствующему числу сочетаний с повторениями: $%\binom{n+2}{3}$%. Из них надо выкинуть все тройки, для которых $%x+y\leqslant z$%. Число таких троек равно $$T(n)=\sum_{i=2}^{n}(n-i+1)[i/2]$$ Здесь $%[i/2]$% - количество пар натуральных чисел на "диагонали" $%x+y=i,\ x\leqslant y$%, а $%n-i+1$% - количество значений, которые может принимать $%z$%, чтобы $%i\leqslant z\leqslant n$%. Нетрудно составить рекуррентное соотношение: $$T(n)=T(n-1)+\sum_{i=2}^n[i/2]=T(n-1)+[n^2/4],\ T(1)=0.$$ Здесь мы использовали свертку $%\sum_{i=2}^n[i/2]=[n^2/4]$%, которая доказывается, например, индукцией по $%n$%. Откуда $$T(n)=\sum_{i=2}^n[i^2/4].$$ Применяя очередную свертку, получим, что $$T(n)=[n(n+2)(2n-1)/24].$$

Итого: $%\binom{n+2}{3}-[n(n+2)(2n-1)/24]$%.

б) В принципе решается аналогично. В ответе будет $%\binom{n}{3}-R(n)$%, где $$R(n)=\sum_{i=2}^{n}(n-i+1)[(i-1)/2]$$

Дальше уже не интересно. в) Тоже понятно как делать, если известны ответы на вопросы а) и б)

Собственно, вопрос: есть ли какое-то "красивое" решение этой задачи? Т.к. мой способ сворачивания формул основан на индукции, а это несколько утомляет.

ссылка

отвечен 22 Апр '14 9:54

Насколько я могу судить, формула для пункта а) верная. Хотя её запись имеет смысл упростить. Эта часть была чисто вычислительная, а вот пункт б) подразумевал некую "олимпиадную" составляющую, которая позволяет не считать отдельно это количество. Там есть связь между одним и другим.

Я выводил рекуррентные формулы отдельно для чётных и нечётных $%n$%. Суммы при этом получались довольно простые, и они хорошо "сворачивались". Соответственно, в пункте в) численный ответ получался сравнительно быстро (или через неравенства, или путём прямой проверки).

(23 Апр '14 0:14) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×861

задан
21 Дек '13 12:32

показан
2601 раз

обновлен
23 Апр '14 0:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru