Билетики
Думаю, большинство моих соотечественников из тех, кто имел дело с программированием, писали программу для определения количества счастливых билетов методом перебора. У меня возник вопрос, можно ли аналитически выразить искомое число. В интернете решил не искать информации по этому поводу, пока не решу сам:) Здесь я приведу решение, но не совсем строгое, некоторые рассуждения, которые кажутся очевидными, не подтверждены доказательствами.
Сначала дадим определение счастливого билета.
Счастливым p,n билетом будем считать билет, номер которого состоит из 2n цифр p-ричной системы счисления, и сумма первых n цифр равняется сумме n последних.
Символом
обозначим количество способов разложить число l с помощью n чисел, каждое из которых не больше p - 1. Ясно, что количество счастливых p,n билетов выражается в виде
Действительно, первые n цифр могут в сумме давать значения от 0 до n*(p-1). Число
будем называть максимально достижимым. Соответственно, для каждого значения 0 <= l <= N существует
вариантов разложения, и данное число умножаются на
вариантов разложения с помощью последних n цифр. Основная трудность заключается в том, чтобы определить
.
Я подошел к этому вопросу с геометрической точки зрения. Рассмотрим n-мерную сетку с шагом 1. Между узлами этой сетки и разложениями чисел существует взаимнооднозначное соответствие: разложению числа l с помощью n чисел
соответствует узел с координатами
.
Ограничение
выражается в рассматривании тех и только тех узлов, которые находятся внутри n-мерного куба со стороной p - 1, находящимся в положительном n-мерном квадранте(имеется в виду множество точек, таких что все их координаты неотрицательны), одна из вершин которого находится в начале координат(звучит громоздко, легче просто поcмоnреть на красный квадрат на картинках). Все искомые узлы, соответствующие разложению числа l лежат на гиперплоскости, отсекающей на координатных осях значения l. Такие гиперплоскости перпендикулярны диагонали куба, исходящей из начала координат. Будем называть эту диагональ основной, а гиперплоскость, которая делит куб пополам и перпендикулярна основной диагонали, будем называть центральной*.
Для наглядности рассмотрим несколько разложений для случая n=2, p = 3.
l = 1 l = 2 l = 3
Точки, обозначенные зеленым цветом нам подходят, красным - нет. В этих рисунках можно усмотреть симметрию и выдвинуть гипотезу:
Числа, соответствующие гиперплоскостям, которые находятся на одинаковом расстоянии от центральной гиперплоскости, имеют одинаковое количество подходящих разложений.
Доказывать строго ее я здесь не буду, ключ в том, что каждому разложению числа l соответствует разложение числа p - l. Используя данную симметрию, для нечетных максимально достижимых N будем иметь
,
а для четных N будем иметь
,
.
Далее, необходимо понять, чему равно число
. Здесь у нас 2 варианта: как мы видим на картинках, разложения одних чисел полностью входят в ограничивающий куб, разложения других частично выходят за его пределы.
Понятно, что ко второй категории чисел относятся все числа, не меньшие основания, и никакие другие.
Разберемся с первой категорией. Заметим, что
для таких чисел равна количеству узлов в n-1 мерном "дискретном" симплексе**(дальше для краткости-просто симплексе) с основанием порядка (l + 1).
Одномерным симплексом с основанием порядка l являются l узлов, лежащих на прямой, двумерным - "слоистый" треугольник, первый слой которого - одномерный симплекс с основанием порядка l, второй - одномерный симплекс с основанием порядка l - 1, и так далее до единицы; трехмерный симплекс - это "слоистая" пирамида из треугольников. Т.е. n-мерным симплексом с основанием порядка l будет последовательность из n-1-мерных симплексов с уменьшающимися порядками оснований, начиная с l, и заканчивая единицей.
Показывать, что
действительно обладает таким свойством можно как минимум двумя способами. Первый - геометрический: доказать, что пересечение гиперплоскости, перпендикулярной основной диагонали куба с кубом, будет являться таким симплексом, второй способ - обратиться к комбинаторному смыслу дискретного симплекса(фиксирование слоя с номером i по координате j в симплексе с основанием порядка l соответствует фиксированию значения i в j позиции разложения числа l - 1, сам же слой соответствует всем разложением числа l - i - 1). Для количества узлов в n-мерном симплексе с основанием порядка l введем обозначение
Теперь рассмотрим вторую категорию. Обозначим за
количество "неправильных" (Wrong) узлов - узлов, которые выходят за границы куба. Тогда имеем
Теперь заметим, что каждой гранями куба отрезаннается симплекс с порядком основания
, таких симплеков n штук. Доказывать это можно тоже либо через комбинаторику, либо через геометрию. Имеем
Осталось научиться считать
. Благодаря слоистой, т.е. рекурсивной структуре, сделать это легко.
Проверим данную формулу на "классическом" случае, вычислим
. Поскольку
нечетно, используем формулу для нечетных N и получаем
Что является верным ответом.
После того, как формула была найдена, я решил покопаться в интернете на предмет аналитических формул и обнаружил, что на википедии есть формула с использованием интеграла и синусов. В журнале "квант" есть целая подборка статей на тему счастливых билетиков, в одной из них я увидел примечание, в котором говорилось о связи гиперкуба и гиперплоскостей с разложением, но дальше эта идея там раскрыта не была. Интересно, мне первому удалось записать формулу в таком виде?:)
* Заметим, что центральная гиперплоскость вовсе не обязательно проходит через вершины куба, как, например, в 2-х мерном случае, в качестве контр примера можно привести трехмерный куб со стороной 1.
** Я это заметил, нарисовав кроме двумерного еще и трехмерный случай, но делать красивую картинку для поста мне было уже лень :(
Сначала дадим определение счастливого билета.
Счастливым p,n билетом будем считать билет, номер которого состоит из 2n цифр p-ричной системы счисления, и сумма первых n цифр равняется сумме n последних.
Символом
обозначим количество способов разложить число l с помощью n чисел, каждое из которых не больше p - 1. Ясно, что количество счастливых p,n билетов выражается в виде
Действительно, первые n цифр могут в сумме давать значения от 0 до n*(p-1). Число
будем называть максимально достижимым. Соответственно, для каждого значения 0 <= l <= N существует
вариантов разложения, и данное число умножаются на
вариантов разложения с помощью последних n цифр. Основная трудность заключается в том, чтобы определить
.
Я подошел к этому вопросу с геометрической точки зрения. Рассмотрим n-мерную сетку с шагом 1. Между узлами этой сетки и разложениями чисел существует взаимнооднозначное соответствие: разложению числа l с помощью n чисел
соответствует узел с координатами
.
Ограничение
выражается в рассматривании тех и только тех узлов, которые находятся внутри n-мерного куба со стороной p - 1, находящимся в положительном n-мерном квадранте(имеется в виду множество точек, таких что все их координаты неотрицательны), одна из вершин которого находится в начале координат(звучит громоздко, легче просто поcмоnреть на красный квадрат на картинках). Все искомые узлы, соответствующие разложению числа l лежат на гиперплоскости, отсекающей на координатных осях значения l. Такие гиперплоскости перпендикулярны диагонали куба, исходящей из начала координат. Будем называть эту диагональ основной, а гиперплоскость, которая делит куб пополам и перпендикулярна основной диагонали, будем называть центральной*.
Для наглядности рассмотрим несколько разложений для случая n=2, p = 3.
l = 1 l = 2 l = 3
Точки, обозначенные зеленым цветом нам подходят, красным - нет. В этих рисунках можно усмотреть симметрию и выдвинуть гипотезу:
Числа, соответствующие гиперплоскостям, которые находятся на одинаковом расстоянии от центральной гиперплоскости, имеют одинаковое количество подходящих разложений.
Доказывать строго ее я здесь не буду, ключ в том, что каждому разложению числа l соответствует разложение числа p - l. Используя данную симметрию, для нечетных максимально достижимых N будем иметь
,
а для четных N будем иметь
,
.
Далее, необходимо понять, чему равно число
. Здесь у нас 2 варианта: как мы видим на картинках, разложения одних чисел полностью входят в ограничивающий куб, разложения других частично выходят за его пределы.
Понятно, что ко второй категории чисел относятся все числа, не меньшие основания, и никакие другие.
Разберемся с первой категорией. Заметим, что
для таких чисел равна количеству узлов в n-1 мерном "дискретном" симплексе**(дальше для краткости-просто симплексе) с основанием порядка (l + 1).
Одномерным симплексом с основанием порядка l являются l узлов, лежащих на прямой, двумерным - "слоистый" треугольник, первый слой которого - одномерный симплекс с основанием порядка l, второй - одномерный симплекс с основанием порядка l - 1, и так далее до единицы; трехмерный симплекс - это "слоистая" пирамида из треугольников. Т.е. n-мерным симплексом с основанием порядка l будет последовательность из n-1-мерных симплексов с уменьшающимися порядками оснований, начиная с l, и заканчивая единицей.
Показывать, что
действительно обладает таким свойством можно как минимум двумя способами. Первый - геометрический: доказать, что пересечение гиперплоскости, перпендикулярной основной диагонали куба с кубом, будет являться таким симплексом, второй способ - обратиться к комбинаторному смыслу дискретного симплекса(фиксирование слоя с номером i по координате j в симплексе с основанием порядка l соответствует фиксированию значения i в j позиции разложения числа l - 1, сам же слой соответствует всем разложением числа l - i - 1). Для количества узлов в n-мерном симплексе с основанием порядка l введем обозначение
Теперь рассмотрим вторую категорию. Обозначим за
количество "неправильных" (Wrong) узлов - узлов, которые выходят за границы куба. Тогда имеем
Теперь заметим, что каждой гранями куба отрезаннается симплекс с порядком основания
, таких симплеков n штук. Доказывать это можно тоже либо через комбинаторику, либо через геометрию. Имеем
Осталось научиться считать
. Благодаря слоистой, т.е. рекурсивной структуре, сделать это легко.
Проверим данную формулу на "классическом" случае, вычислим
. Поскольку
нечетно, используем формулу для нечетных N и получаем
Что является верным ответом.
После того, как формула была найдена, я решил покопаться в интернете на предмет аналитических формул и обнаружил, что на википедии есть формула с использованием интеграла и синусов. В журнале "квант" есть целая подборка статей на тему счастливых билетиков, в одной из них я увидел примечание, в котором говорилось о связи гиперкуба и гиперплоскостей с разложением, но дальше эта идея там раскрыта не была. Интересно, мне первому удалось записать формулу в таком виде?:)
* Заметим, что центральная гиперплоскость вовсе не обязательно проходит через вершины куба, как, например, в 2-х мерном случае, в качестве контр примера можно привести трехмерный куб со стороной 1.
** Я это заметил, нарисовав кроме двумерного еще и трехмерный случай, но делать красивую картинку для поста мне было уже лень :(