|
Не так давно мы проводили межвузовскую студенческую олимпиаду. Я придумал для неё одну задачу, которая в итоговый список не вошла, и я хочу предложить её здесь. Решение принимается только с полным доказательством. Пусть $%n$% -- натуральное число. Рассматриваются все треугольники с целочисленными сторонами, длины каждой из которых не превосходят $%n$%. а) Сколько имеется таких треугольников для каждого $%n$%? б) Сколько имеется разносторонних треугольников с тем же свойством? в) При каком наименьшем значении $%n$% разносторонних треугольников будет больше половины от числа всех? задан 21 Дек '13 12:32 
falcao |
|
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$%
Вынуждена написать по частям. Так что продолжение следует. отвечен 22 Дек '13 22:22 
ASailyan Решение пока не дописано до конца, поэтому я не хотел бы его подробно комментировать, но пока что обращаю внимание, что мы учитываем не тройки длин $%(x,y,z)$%, а сами треугольники, каждый из которых должен учитываться ровно один раз. В этом смысле $%(2;3;4)$% и $%(3;4;2)$% и т.п. -- одно и то же. P.S. Картинка в самом низу мне в данный момент не видна.
(23 Дек '13 0:24)
falcao
|
|
а) Число способов составить тройки натуральных чисел $%(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 
cartesius Насколько я могу судить, формула для пункта а) верная. Хотя её запись имеет смысл упростить. Эта часть была чисто вычислительная, а вот пункт б) подразумевал некую "олимпиадную" составляющую, которая позволяет не считать отдельно это количество. Там есть связь между одним и другим. Я выводил рекуррентные формулы отдельно для чётных и нечётных $%n$%. Суммы при этом получались довольно простые, и они хорошо "сворачивались". Соответственно, в пункте в) численный ответ получался сравнительно быстро (или через неравенства, или путём прямой проверки).
(23 Апр '14 0:14)
falcao
|