офтоп
Не в меру развеселилась, со вчерашнего вечера. Действительно, только суровый профессиональный математик мог решить задачу №1 производящими функциями. Правда, он или недостаточно суров, или недостаточно профессионален. Надо было для определения к-та с помощью интегральной т-мы Коши вычеты посчитать.
Задача о лапах и общая постановка вопроса
Задача о лапах и общая постановка вопроса
Последний раз редактировалось Swetlana 27 ноя 2019, 18:54, всего редактировалось 1 раз.
Причина: test
Причина: test
Задача о лапах и общая постановка вопроса
Юрий Олеша кутил в ресторане (видимо, допрокучивал гонорар за экранизацию "Трёх толстяков"). В какой-то момент он решил уходить, увидел человека в униформе, и между ними состоялся следующий диалог.Володиславир писал(а):Source of the post n = 6 просто не подходит к условию задачи.
О. - Официант, подайте такси.
А. - Я не официант, а адмирал.
О. -Тогда подайте катер!
Vlardenir, проверьте ваше решение для небольшого n, даже если вы адмирал.
Последний раз редактировалось Swetlana 27 ноя 2019, 18:54, всего редактировалось 1 раз.
Причина: test
Причина: test
Задача о лапах и общая постановка вопроса
Проверила полученную формулу для n=2, 4, 6, 8, 10 и 306.
Количество разбиений подсчитывала с помощью программы))
Количество разбиений подсчитывала с помощью программы))
Последний раз редактировалось Swetlana 27 ноя 2019, 18:54, всего редактировалось 1 раз.
Причина: test
Причина: test
Задача о лапах и общая постановка вопроса
Всё-таки накосячила. Простите слабомыслящую
...остаток
, набираемый двойками и четвёрками, равен или 0, или 2, или 4.
То есть случай
не надо рассматривать отдельно, если остаток равен 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.$$ $$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.$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%241%2B%5Cleft%20%5Clfloor%20%5Cfrac%7B4%7D%7B4%7D%20%5Cright%20%5Crfloor%3D2%2C%201%2B%5Cleft%20%5Clfloor%20%5Cfrac%7B2%7D%7B4%7D%20%5Cright%20%5Crfloor%3D1%2C%201%2B%5Cleft%20%5Clfloor%20%5Cfrac%7B0%7D%7B4%7D%20%5Cright%20%5Crfloor%3D1.%24%24)
Теперь формула верна для всех чётных
, что, конечно, радует))
![$$\sum_{i=0}^{\left \lfloor\frac{n}{6} \right \rfloor }(1+\left \lfloor \frac{n-6i}{4} \right \rfloor)$$ $$\sum_{i=0}^{\left \lfloor\frac{n}{6} \right \rfloor }(1+\left \lfloor \frac{n-6i}{4} \right \rfloor)$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24%5Csum_%7Bi%3D0%7D%5E%7B%5Cleft%20%5Clfloor%5Cfrac%7Bn%7D%7B6%7D%20%5Cright%20%5Crfloor%20%7D%281%2B%5Cleft%20%5Clfloor%20%5Cfrac%7Bn-6i%7D%7B4%7D%20%5Cright%20%5Crfloor%29%24%24)
Хорошо бы её преобразовать и упростить, но пока не соображу, как.
ЗЫ. В предпредыдущем посте исправила, исправленному верить))
...остаток
То есть случай
Теперь формула верна для всех чётных
Хорошо бы её преобразовать и упростить, но пока не соображу, как.
ЗЫ. В предпредыдущем посте исправила, исправленному верить))
Последний раз редактировалось Swetlana 27 ноя 2019, 18:54, всего редактировалось 1 раз.
Причина: test
Причина: test
Задача о лапах и общая постановка вопроса
Задача №2. Коммутативное разложение на двойки, тройки, четвёрки.
Сколько существует последовательностей
таких, что ![$$2\lambda _2 + 3\lambda _3+4\lambda _4=n, n\geq 2.$$ $$2\lambda _2 + 3\lambda _3+4\lambda _4=n, n\geq 2.$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%242%5Clambda%20_2%20%2B%203%5Clambda%20_3%2B4%5Clambda%20_4%3Dn%2C%20n%5Cgeq%202.%24%24)
Буду делать аккуратно, чтобы не накосячить. Возможно, полученные формулы удастся объединить в одну.
Случай 1.![$$n=2k, k=1, 3, 4,...$$ $$n=2k, k=1, 3, 4,...$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24n%3D2k%2C%20k%3D1%2C%203%2C%204%2C...%24%24)
Количество троек в разбиении чётно, а именно![$$2i, i=0...\left \lfloor \frac{n}{6} \right \rfloor.$$ $$2i, i=0...\left \lfloor \frac{n}{6} \right \rfloor.$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%242i%2C%20i%3D0...%5Cleft%20%5Clfloor%20%5Cfrac%7Bn%7D%7B6%7D%20%5Cright%20%5Crfloor.%24%24)
Если троек
, то вклад троек в сумму равен
, остаток, набираемый двойками и четвёрками, равен
или
, или
, разбиение существует, для 0 и 2 одно, для 4 - два.
Для остальных
остаток
и чётен. Подсчитаем количество его разбиений на единицы и двойки.
Т.к.
чётно, то количество разбиений на двойки и четвёрки равно количеству разбиений
на единицы и двойки.
Отсюда общее количество разбиений равно
.
Сколько существует последовательностей
Буду делать аккуратно, чтобы не накосячить. Возможно, полученные формулы удастся объединить в одну.
Случай 1.
Количество троек в разбиении чётно, а именно
Если троек
Для остальных
Т.к.
Отсюда общее количество разбиений равно
Последний раз редактировалось Swetlana 27 ноя 2019, 18:54, всего редактировалось 1 раз.
Причина: test
Причина: test
- Володиславир
- Сообщений: 122
- Зарегистрирован: 28 окт 2015, 21:00
Задача о лапах и общая постановка вопроса
Swetlana писал(а):Source of the post Vlardenir, проверьте ваше решение для небольшого n, даже если вы адмирал.
Так, у меня решение самое брутальное - тупым перебором.
И того q = 3
В общем, не понял
Наверное, Вы меня к чему-то подводите как бычка.
Последний раз редактировалось Володиславир 27 ноя 2019, 18:54, всего редактировалось 1 раз.
Причина: test
Причина: test
- Володиславир
- Сообщений: 122
- Зарегистрирован: 28 окт 2015, 21:00
Задача о лапах и общая постановка вопроса
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 для заданного уравнения:
Как-то так и получился частный случай с НОК( ).
Так как с комбинаторикой знаком, лишь поверхностно, а будет правильно сказать, что не знаком, то задачку решал исключительно из своих соображений.
Получилось вот что:
Найти количество решений в целых числах у уравнения:
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 для заданного уравнения:
Как-то так и получился частный случай с НОК( ).
Последний раз редактировалось Володиславир 27 ноя 2019, 18:54, всего редактировалось 1 раз.
Причина: test
Причина: test
Задача о лапах и общая постановка вопроса
Ха, проходит. Если в формулу для n подставить 0, то как раз одно разбиение и получится.
Хорошая формула , только непонятно, как её упростить.
Хорошая формула , только непонятно, как её упростить.
Последний раз редактировалось Swetlana 27 ноя 2019, 18:54, всего редактировалось 1 раз.
Причина: test
Причина: test
Задача о лапах и общая постановка вопроса
Не поняла вашу формулу с НОКом, проверить ваше решение не могу. Проверка решения - дело рук самого решающего, для комбинаторных формул, во всяком случае. Я программу в делфях написала, себе не верю, все свои формулы проверяю. Вот сейчас (не веря своему доказательству и своему щастию, что и для нечётных n задача уже решена) проверила, до n=307. Совпадает ли тупой перебор для нечётного n с формулой числа разбиений чётного n-3. Совпадает.
Лемма.
Число разбиений
Доказательство.
У любого нечётного
Вот для n=3 не проходит. Для него есть одно разбиение, а для 0 разбиений нет.
Последний раз редактировалось Swetlana 27 ноя 2019, 18:54, всего редактировалось 1 раз.
Причина: test
Причина: test
Задача о лапах и общая постановка вопроса
Количество коммутативных разбиений на двойки, тройки, четвёрки для любого натурального
равно
для чётного ![$$n$$ $$n$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24n%24%24)
и
для нечётного ![$$n.$$ $$n.$$](http://fx.ifz.ru/tex2.php?d=120&i=%24%24n.%24%24)
и
Последний раз редактировалось Swetlana 27 ноя 2019, 18:54, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 2 гостей