Интересная задача о треугольника Паскаля: значения кратные p

[Whitaker]

Вот посмотрите на картинку пожалуйста.
Я заметил вот такую удивительную вещь:
То что на картинке выделено зеленым оказывается это сумма двух выделенных желтым цветом по модулю 5.
А то что серым - сумма трех выделенных желтым по модулю 5.
А то что голубым - сумма четырех выделенных желтым по модулю 5.
Интересная вещь получается
Как это доказать то?
Наверное решение задачи "держится" именно на этом??

[Sonic86]

По-моему, это уход в сторону. Вам Null в 1-м своем посте написал последовательность действий, делайте их.

[Whitaker]

Sonic86 в сообщении #489814 писал(а):

По-моему, это уход в сторону. Вам Null в 1-м своем посте написал последовательность действий, делайте их.

Я хочу определить количество чисел не кратных $p$ в строчках $0,1,...,p^k-1$ (это то что советовал Null). Вы конечно написали в предыдущем посте как это сделать, но к сожалению у меня никак не получается. Я не представляю как это сделать. Для меня именно этот пункт задачи кажется трудной. Остальное вытекает из него.

[Whitaker]

Sonic86 в сообщении #489422 писал(а):

Выделите закрашенные треугольники, соответствующие $N(p-1)$. Посмотрите на остальную часть картинки.

Но ведь закрашенных треугольник, соответствующие $N(p-1)$ ведь нет.
Кстати, у Вас $N(p-1)$-количество элементов делящиеся на $p$ да??

[Sonic86]

Whitaker в сообщении #489931 писал(а):

Но ведь закрашенных треугольник, соответствующие $N(p-1)$ ведь нет.

Наврал. Имелись ввиду строки с номерами $p,...,2p-1$

Whitaker в сообщении #489931 писал(а):

Кстати, у Вас $N(p-1)$-количество элементов делящиеся на $p$ да??

Да, $N(m)$ - число биномиальных коэффициентов с нижним индексом не большим $m$, делящихся на $p$.

Аналогичная задачка, хотя более простая:Построить рекуррентное соотношение для площади снежинки Коха:
(http://ru.wikipedia.org/wiki/%D0%9A%D1% ... 1%85%D0%B0)
Снежинка Коха $K = \bigcup\limits_n K_n$, где $K_n$ - $n$-ая итерация снежинки. Площади снежинки и $n$-ой итерации снежинки обозначим $S,S_n$. Тогда $S_1 = \frac{a^2 \sqrt{3}}{4}$, $S_{n+1}=S_n+3^n \frac{ \left( \frac{a}{3^n} \right)^2 \sqrt{3}}{4}$.

[Whitaker]

Задача о снежинке Коха я понял и она намного легче.
Никак не могу разобрать эту подзадачу.
Сколько существует элементов не кратных $p$ в строках с номерами $0,1,....,p^k-1$

[Whitaker]

Sonic86 в сообщении #489422 писал(а):

Whitaker в сообщении #489418 писал(а):

У меня получилось следующее: В любой строчке вида $p^k-1$ ни один элемент не делится на простое число $p$.

То, что в строке с номером $p^k-1$ биномиальные коэффициенты на $p$ не делятся, это понятно.

Whitaker в сообщении #489418 писал(а):

А вот определить количество чисел не кратных $p$ в строках от $0$ до $p^k-1$ я не знаю как делать

Ну при $k=1$ формула у Вас уже есть. Дальше надо рекуррентно задавать.
Обозначим искомое число $N(m)$.
Попробуйте, для простоты, посчитать $N(p^2-1)$, выразить его через $N(p-1)$. Посмотрите на картинку. Выделите закрашенные треугольники, соответствующие $N(p-1)$. Посмотрите на остальную часть картинки. Есть ли в ней нечто похожее на треугольник, соответствующий $N(p-1)$. Если есть, то как это считать? Есть ли в ней нечто непохожее на треугольник, соответствующий $N(p-1)$. Если есть, то как это считать? Потом все сложите.

Sonic86 я вычислил величину $N(p^2-1)$, как Вы просили.
Оказывается, что $N(p^2-1)=\Big[N(2p-1)\Big]^2=\dfrac{p^2(p-1)^2}{4}$

[Sonic86]

Дальше можно делать так:
Найдем $N(p^3-1)$. Смотрим на картинку. Биномиальные коэффициенты в строках с номерами $0,...,p^k-1$ сгруппированы в треугольники двух типов:
1-й тип - треугольники сгруппированы так, как и треугольники в строках $0,...,p^2-1$.
2-й тип - оставшиеся большие треугольники.
Треугольников 1-го типа ровно $1+2+...+p=\frac{p(p+1)}{2}$, причем в каждом треугольнике, как Вы уже нашли, $\frac{(p(p-1))^2}{4}$ чисел, значит всего $\frac{p^3(p-1)^2(p+1)}{8}$.
Треугольников 2-го типа ровно $1+2+...+(p-1)=\frac{p(p-1)}{2}$, причем в каждом таком треугольнике $1+2+...+p^2-1=\frac{p^2(p^2-1)}{2}$ чисел, а значит всего в треугольниках 2-го типа $\frac{p^3(p^2-1)(p-1)}{4}$
$N(p^3-1)= \frac{p^3(p-1)^2(p+1)}{8} + \frac{p^3(p^2-1)(p-1)}{4}=\frac{3p^3(p-1)^2(+1)}{8}$.
Вычисление дальше происходит аналогично.

Что-то меня смутные сомнения терзают - сложновато получается

[Whitaker]

Ну да вычисления очень громоздкие

[Null]

$N(p^k-1)=\left(\frac{p(p+1)}{2}\right)^k$

Зря вы 1ый пункт об 1 строчке игнорируете.

[Whitaker]

Аа как Вы это получили, Null?
Можете рассказать?

-- Пт окт 07, 2011 17:49:43 --

И как задача отсюда решается?

[Null]

Что значит что $C_n^l$ не делиться на $p$? Это значит что при сложении $l$ и $n-l$ не происходит перехода через разряд. То есть $N(p^k-1)$($p^k-1\ge n \ge l\ge 0$) равно количеству пар строк длинны $k$(с ведущими 0) таких что каждая цифра первой строки больше соответствующей цифры второй строки. Теперь считаем количество возможных вариантов пар цифр и возводим в $k$тую степень.


Конечно же $N(l)$ - количество не делящихся в строках $0..l$ (их $l+1$)

[Whitaker]

А как тогда задача решается?

-- Пт окт 07, 2011 18:13:05 --

Whitaker в сообщении #490424 писал(а):

А как тогда задача решается?

Извините, а что означает "переход через разряд" ?