Задача о лапах и общая постановка вопроса

Swetlana · Сообщение **Swetlana** » 31 окт 2015, 06:12

офтоп
Не в меру развеселилась, со вчерашнего вечера. Действительно, только суровый профессиональный математик мог решить задачу №1 производящими функциями. Правда, он или недостаточно суров, или недостаточно профессионален. Надо было для определения к-та с помощью интегральной т-мы Коши вычеты посчитать.

Swetlana · Сообщение **Swetlana** » 31 окт 2015, 06:20

Володиславир писал(а):Source of the post n = 6 просто не подходит к условию задачи.

Юрий Олеша кутил в ресторане (видимо, допрокучивал гонорар за экранизацию "Трёх толстяков"). В какой-то момент он решил уходить, увидел человека в униформе, и между ними состоялся следующий диалог.
О. - Официант, подайте такси.
А. - Я не официант, а адмирал.
О. -Тогда подайте катер!
Vlardenir, проверьте ваше решение для небольшого n, даже если вы адмирал.

Swetlana · Сообщение **Swetlana** » 31 окт 2015, 14:06

Проверила полученную формулу для n=2, 4, 6, 8, 10 и 306.
Количество разбиений подсчитывала с помощью программы))

Swetlana · Сообщение **Swetlana** » 31 окт 2015, 14:23

Всё-таки накосячила. Простите слабомыслящую
...остаток $n-6\left \lfloor \frac{n}{6} \right \rfloor$ , набираемый двойками и четвёрками, равен или 0, или 2, или 4.
То есть случай $i=\left \lfloor \frac{n}{6} \right \rfloor$ не надо рассматривать отдельно, если остаток равен 4, то общая формула дает для четвёрки 2 разбиения, а для 0 или 2 одно:
$1+\left \lfloor \frac{4}{4} \right \rfloor=2, 1+\left \lfloor \frac{2}{4} \right \rfloor=1, 1+\left \lfloor \frac{0}{4} \right \rfloor=1.$
Теперь формула верна для всех чётных $n\geq2$ , что, конечно, радует))
$\sum_{i=0}^{\left \lfloor\frac{n}{6} \right \rfloor }(1+\left \lfloor \frac{n-6i}{4} \right \rfloor)$
Хорошо бы её преобразовать и упростить, но пока не соображу, как.
ЗЫ. В предпредыдущем посте исправила, исправленному верить))

Swetlana · Сообщение **Swetlana** » 31 окт 2015, 14:30

Задача №2. Коммутативное разложение на двойки, тройки, четвёрки.
Сколько существует последовательностей $(\lambda _2,\lambda _3, \lambda _4)$ таких, что $2\lambda _2 + 3\lambda _3+4\lambda _4=n, n\geq 2.$
Буду делать аккуратно, чтобы не накосячить. Возможно, полученные формулы удастся объединить в одну.
Случай 1. $$n=2k, k=1, 3, 4,...$$

Количество троек в разбиении чётно, а именно $2i, i=0...\left \lfloor \frac{n}{6} \right \rfloor.$
Если троек $2\left \lfloor \frac{n}{6} \right \rfloor$ , то вклад троек в сумму равен $6\left \lfloor \frac{n}{6} \right \rfloor$ , остаток, набираемый двойками и четвёрками, равен $n-6\left \lfloor \frac{n}{6} \right \rfloor=0$ или $$2$$

, или

, разбиение существует, для 0 и 2 одно, для 4 - два.
Для остальных $$i$$

остаток $n-6i\geq 4$ и чётен. Подсчитаем количество его разбиений на единицы и двойки.
Т.к. $$n-6i$$

чётно, то количество разбиений на двойки и четвёрки равно количеству разбиений $\frac{n-6i}{2}$ на единицы и двойки.
Отсюда общее количество разбиений равно $a_{n}=\sum_{i=0}^{\left \lfloor\frac{n}{6} \right \rfloor }(1+\left \lfloor \frac{n-6i}{4} \right \rfloor)$ .

Володиславир

Swetlana писал(а):Source of the post Vlardenir, проверьте ваше решение для небольшого n, даже если вы адмирал.

Так, у меня решение самое брутальное - тупым перебором.
$6 = \left\{\begin{matrix} 2+2+2\\ 2+4\\ 3+3 \end{matrix}\right.$
И того q = 3
В общем, не понял
Наверное, Вы меня к чему-то подводите как бычка.

Володиславир

Swetlana: "С НОК-ом не поняла."
Так как с комбинаторикой знаком, лишь поверхностно, а будет правильно сказать, что не знаком, то задачку решал исключительно из своих соображений.
Получилось вот что:
Найти количество решений в целых числах у уравнения:
2x+3y+4z = 306 при x, y, z ≠ 0

По условию x, y, z ≠ 0 значит хотя бы по одному разу числа 2, 3, 4 входят в уравнение. Просумируем их 2+3+4 = 9 и вычтем из 306. Теперь будем иметь дело с числом 297.
Так как необходимо учесть все комбинации чисел 2, 3 и 4, то ищем НОК (наименьшее общее кратное) трёх чисел. Очевидно, что НОК(2, 3, 4) = 12.
Теперь можно найти все комбинации сумм для 12:
2+2+2+2+2+2
4+2+2+2+2
4+4+2+2
4+4+4
3+3+3+3
3+3+2+2+2
3+3+4+2
Имеем 7 комбинаций.
Далее, воспользуемся модульностью по НОК(2, 3, 4):
297 mod 12 = 9, т.е. получаем целочисленный остаток от деления на 12, и нужно найти комбинации для числа 9:
3+3+3
2+2+2+3
2+3+4
Имеем 3 комбинации.
Далее, вычитаем остаток 9 из 297 и делим на 12
(297-9)/12 = 24
Теперь остаётся подсчитать общее количество комбинаций чисел 2, 3, 4 для заданного уравнения:

Как-то так и получился частный случай с НОК( ).

Swetlana · Сообщение **Swetlana** » 31 окт 2015, 17:49

Ха, проходит. Если в формулу для n подставить 0, то как раз одно разбиение и получится.
Хорошая формула , только непонятно, как её упростить.

Swetlana · Сообщение **Swetlana** » 31 окт 2015, 17:50

Не поняла вашу формулу с НОКом, проверить ваше решение не могу. Проверка решения - дело рук самого решающего, для комбинаторных формул, во всяком случае. Я программу в делфях написала, себе не верю, все свои формулы проверяю. Вот сейчас (не веря своему доказательству и своему щастию, что и для нечётных n задача уже решена) проверила, до n=307. Совпадает ли тупой перебор для нечётного n с формулой числа разбиений чётного n-3. Совпадает.
Лемма.
Число разбиений $b_{n}$ (на двойки, тройки, четвёрки) для любого нечётного $n, n\geq 3$ , равно $a_{n-3}$ .
Доказательство.
У любого нечётного $n\geq 3$ в каждом разбиении есть хотя бы одна тройка. Рассмотрим все разбиения для нечётного $$n$$

. Удалим из каждого разбиения одну тройку и получим разбиения для чётного $$n-3$$

. Предположим, что мы получили не все разбиения для $$n-3$$

, а только их часть. Но тогда, добавив к отсутствующим разбиениям для $$n-3$$

тройку, получим новые разбиения для $$n$$

. Пришли к противоречию с тем, что рассмотрены все разбиения для $$n.$$

$b_{n}=a_{n-3}$ .
Вот для n=3 не проходит. Для него есть одно разбиение, а для 0 разбиений нет.

Swetlana · Сообщение **Swetlana** » 31 окт 2015, 17:58

Количество коммутативных разбиений на двойки, тройки, четвёрки для любого натурального $n, n\geq 2$ равно
$a_{n} = \sum_{i=0}^{\left \lfloor\frac{n}{6} \right \rfloor }(1+\left \lfloor \frac{n-6i}{4} \right \rfloor)$ для чётного $$n$$

и
$a_{n} = \sum_{i=0}^{\left \lfloor\frac{n-3}{6} \right \rfloor }(1+\left \lfloor \frac{n-3-6i}{4} \right \rfloor)$ для нечётного $$n.$$

yourdomain.com