Задачки по дискретной математике

Panda
ну, что сказать тебе про Сахалин?))

 

Panda
Дык строка
k1 k2 k3 k4
0 0 5 3

неправильная, ведь сумма k1 + k2 + k3 + k4 = 5, а у тебя получается 8.

И последняя строчка
1 1 0 3 -16
тоже неправильная, должно получиться не -16, а другое число. Проверь аккуратнее!

 

crypto
тьфу, блин, ну я и раззява. Все проверила, нашла еще 1 ошибку и все получилось!
Большое спасибо!!!

 

Panda
В таком случае для закрепления пройденного найди явное выражение для N-го числа Фибоначчи.

 

crypto

хм, наверное это будет глупо спрашивать - но это что, из той же темы?

 

Panda
Задачка из дискретной математики. Искомое число равно коэффициенту при x^N в разложении "достаточно простой" функции (точнее функции вида 1/(ax² + bx + c)).
А вообще забей, это была шютка

 

crypto
Понятно. Ну, с числами Фибоначчи мы сталкивались в курсе вычислительной математики - нелинейные уравнения решали. Но на тренировку времени совершенно нет. В этот раз над нами злобно пошутил деканат - экзаменационная сессия через 2 месяца после установочной, в то время как обычно на это давали 4 месяца. А назадавали выше крыши. Так что дай Бог, успеть бы выполнить обязательную программу. А произвольную катать будем потом.

Есть еще 2 задачки - поможешь?
1) Сколько существует чисел, не превосходящих 1000, которые:
а) делятся одновременно на 6 и на 15;
б) делятся на 6 или на 15?

2) Сколько существует 9-значных чисел, сумма цифр которых четна?

 

Panda
Задачка 1 теретико-множественная. Пусть A и B - два множества чисел, имеющих непустое пересечение C, тогда, как тебе должно быть известно (формула включения-исключения), мощность объединения множеств A и B равна сумме мощностей этих множеств, минус мощность пересечения. К чему это, сейчас поймешь.

Вот у нас есть множество A натуральных чисел (не превосходящих 1000, т.е. <= 1000), делящихся на 6, и множество B натуральных чисел (<= 1000), делящихся на 15.
Множество C (пересечение A и B) - это все натуральные числа (<= 1000), делящиеся на 30 (30 - наименьшее общее кратное 6 и 15).
Значит, на вопрос а) (сколько существует чисел, не превосходящих 1000, которые делятся одновременно на 6 и на 15) мы отвечаем, что их количество равно мощности множества C, т.е. [1000/30], гле [N] - целая часть N.
А на вопрос б) ответ будет: [1000/6] + [1000/15] - [1000/30].

 

Panda
Вторая задачка: предполагаем, что первая цифра 9-значного числа не 0 (т.е. истинно 9-значное число). Пусть оно имеет вид
a1,a2,a3,a4,a5,a6,a7,a8,a9.

Только один вопрос: тебе известно, что число решений уравнения
x1+...+xn = N в целых неотрицательных числах равно C(N + n - 1, n - 1) (C(n, m) - биномиальный коэффициент)?

 

del

 

Mikl___
[1000/30] = 33

 

Panda
Вторую задачку могу объяснить через производящие функции, если такие проходили.

 

Mikl___
Метод перебора - прекрасная вещь. Но в данном случае можно решить в общем виде.
0

 

crypto

Нам давали, что число решений этого уравнения С(n,m), где С(n,m) - это сочетание с повторениями. Без повторений это сочетание будет выглядеть так: C(n+m-1,n).

Производящие функции мы не проходили.

Mikl___
Спасибо за помощь, но, боюсь, что препод захочет именно теоретического обоснования.

 

Про вторую: любому девятизначному числу а1_а2_а3_..._а9 поставим в соответствие число (9-а1)_(9-а2)_..._(9-а9), которое ставится однозначно каждому числу и наоборот, причем суммы цифр у чисел в паре имеют разные четности, таким образом все 9-значные числа не начинающиеся с 9 разбиваются на 2 группы с четной и нечетной суччой цифр, среди них с четной суммой будет 9*10^8/2 , осталось посчитать количество 8-ми и меньше-значных чисел с нечетной суммой цифр, но их опять же будет ровно половина, т.к. любому 8-мизначному а1_а2_..а8 ставим в соответствие
(а1)_(9-а2)_(9-а3)_.._(9-а8), таким образом получается, что всего 9*10^8/2+10^8/2 = 5*10^8, нигде не ошибся?

 

Panda
Вторую задачку легко решить рекурсивно (по индукции).
Рассмотрим все 1-значные числа. Их 10: от 0 до 9. 5 из них имеет четную сумму цифр, 5 - нечетную.
Теперь рассмотрим 2-значные числа, в том числе начинающиеся на 0. Зачем это нужно, будет видно из дальнейшего. Все двузначные числа можно получить из 1-значных путем приписывания к первой цифре числа (от 0 до 9) всех 1-значных чисел.
Например,
10 11 12 13 14 15 16 17 18 19 ...
Теперь посмотрим, как меняется четность суммы цифр. Если первая цифра А четная, то с четной суммой цифр среди получающихся 2-значных чисел вида АВ будет 5, а с нечетной суммой - тоже 5. То же самое будет и для нечетной первой цифры. Итого 2-значных чисел с четной суммой будет 10*5, и с нечетной 10*5. Но если 2-значное число начинается с 1, то чисел с четной суммой цифр будет уже 9*5=45, и с нечетной - тоже 45. Всего 90, как и должно быть.

Для 3-значных с четной суммой 9*50=450, и с нечетной 450, итого 900.

Дальше по индукции и наверное ты уже сама сможешь доказать, что искомое число равно 450000000.

 

crypto

продолжая аналогию получим, что чисел с нечётной суммой цифр тоже 450000000...
итого остаётся 1000000000 - 2*450000000 = 100000000 чисел сумма цифр которых не является ни чётной, ни нечётной ))

Получается Velheart прав - чисел с четной суммой цифр половина от общего количества
Правда при условии, что числа с ведущими нулями не отбрасываются как не 9-значные.

Кстати проходил С(n,m), C(n+m-1,n) шибко давно и малость подзабыл...
C(n+m-1,n) это количество возможностей разложить m разных предметов по n позиций для них, причём в разных позициях могут быть одинаковые предметы, или нет?