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

[Whitaker]

Ну да согласен с Вами.
Вопрос покажется глупым, а причем тут $\overline{k_d \dots k_0}_{(p)}=k_dp^d+k_{d-1}p^{d-1}+...+k_1p+k_0=k$?

[Null]

Вы спросили что это обозначает.

[Whitaker]

Я понял что Вы имели ввиду. Сейчас я попробую решить задачу в той последовательности в который Вы указали.

[Sonic86]

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

Что значит числу переносов при сложении стобликом в p-ичной системе?

Вы когда 2 числа с $k$ разрядами складываете столбиком (пишите одно сверху, второе снизу, проводите черту, под чертой пишите результат справа налево и т.д. как в школе). Перенос - это то, что называется "один в уме" при таком сложении.

[Whitaker]

Null в сообщении #489291 писал(а):

Я бы стал делать так:
1. Сколько чисел не кратных $p$ лежит в $\overline{k_d \dots k_0}_{(p)}$ строчке.
2. Сколько их в строчках 0..N Где N=
a) $p-1$
б) $p^k-1$
в) $p^k$
г) $a p^k$ где a цифра.
д) для любого N=$\overline{k_d \dots k_0}_{(p)}$

Вот сейчас я думаю над пунктом 1, но пока безрезультатно. Подскажите пожалуйста что-нибудь.

[Sonic86]

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

Вот сейчас я думаю над пунктом 1, но пока безрезультатно. Подскажите пожалуйста что-нибудь.

Посмотрите на картинку, на строки треугольника с номерами $1,...,p-1$. Какую фигуру они образуют? Сколько в ней элементов?

[Whitaker]

Sonic86 Рассмотрим строки треугольника Паскаля с номерами $0,1, 2,..., p-1$. В полученном треугольника всего $1+2+3+...+p=\dfrac{p(p+1)}{2}$ элементов.

[Sonic86]

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

Sonic86 Рассмотрим строки треугольника Паскаля с номерами $0,1, 2,..., p-1$. В полученном треугольника всего $1+2+3+...+p=\dfrac{p(p+1)}{2}$ элементов.

Ну вот, замечательно, только вроде бы не $\frac{p(p+1)}{2}$, а $\frac{p(p-1)}{2}$ (при $p=3$ должно быть 3 элемента).
Теперь думайте над 2-й задачей, используйте рекуррентные соотношения.

[Whitaker]

Sonic86 извините пожалуйста, а почему $\dfrac{p(p-1)}{2}$?
В 0-й строке 1 элемент, в 1-й строке 2 элемента,.... в (p-1)-й строке p элементов.
Всего получим $1+2+3+...+p=\dfrac{p(p+1)}{2}$. Ведь здесь никак не будет $\dfrac{p(p-1)}{2}$
Но мы ведь даже пока не решили задачу под пунктом 1?
Под 2-й задачей какую Вы имеет ввиду? Ведь их там несколько штук.

-- Вт окт 04, 2011 15:57:20 --

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

[Sonic86]

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

Sonic86 извините пожалуйста, а почему $\dfrac{p(p-1)}{2}$?
В 0-й строке 1 элемент, в 1-й строке 2 элемента,.... в (p-1)-й строке p элементов.

Видимо, потому, что в $k$-й строке $k$ элементов, делящихся на $p$. (для $0$-й строки имеем $C_0^0=1$ - не делится на $p$).
Кроме того - я по картинке смотрел - в верхнем желтом треугольнике 3 ячейки.
Или Вы уже считаете число биномиальных коэффициентов, не делящихся на $p$? Я считал делящиеся.

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

Под 2-й задачей какую Вы имеет ввиду? Ведь их там несколько штук.

эту:

Null в сообщении #489291 писал(а):

б) $p^k-1$

[Whitaker]

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

[Sonic86]

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)$. Если есть, то как это считать? Потом все сложите.

[Whitaker]

Для наглядности вот треугольник Паскаля по модулю $5$

[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]

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

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

Пишите что конкретно не получается. На мой взгляд это - самый интересный момент в задаче.