Докажете, че... - една нелесна задача

[rashi101]

Докажете, че броят на начините, по които можете да представите естественото число n като сбор от други естествени числа, които не са кратни на 3, е равен на броя начини, по които можете да го представите като сбор на ест. числа, никое от които не се повтаря повече от 2 пъти.
Например 5 = 1+1+1+1+1 = 1+1+1+2 = 1+2+2 = 1+4 (4 начина) и 5= 1+1+3 = 1+2+2 = 2+3 = 1+4 (отново 4 начина).

[rashi101]

Кажете да дам ли някаква подсказка? Задачата наистина е доста сложна.

[ins-]

Задачата е хубава, но за съжаление нямам време да я мисля сериозно
От къде е? Ако известно време никой не я реши - ще е добре да пуснеш жокер, но не вярвам да
остане нерешена.

[martin.nikolov]

Ако човек се сети да използва пораждащи функции (които се използват често за такива задачи), задачата става доста лесна.

[drago]

Ако човек се сети да използва пораждащи функции (които се използват често за такива задачи), задачата става доста лесна.

По принцип е възможно, но много ще ми е интересно как ще стане ?!
Решението: Идеята е някакво съответствие м/у двата начина на представяния.
Нека X1=множеството на възможните представяния на n като сума, така че има поне 1 число, което се повтаря поне 3 пъти.
X2=множеството на възможните предтавяния на n като сума, така че има поне едно число което е кратно на 3.
Задачата е еквивалентна да докажем, че |X1|=|x2|.
Нека Y1 = X1\X2, Y2=X2\X1.
Остава да покажем, че: |Y1|=|Y2|.
Построяваме съответствие F: Y2 -> Y1.
Ako {x1,...,xs, 3^k1.y1,...,3^km.ym}e oт Y2 (x1,...,xs,y1,...,ym не се делят на 3, а измежду x1,...,xs няма някое което се повтаря повече от 2 пъти.) Съпоставяме: {x1,...xs, y1,...(3^k1 пъти), ..., ym(3^km пути) }. то е от Y1.
Остава да се съобрази, че F e върху и 1-1.

[martin.nikolov]

Пораждащата фунция за броя на начините по които може да се представи дадено естествено число като сума на естествени, които се повтарят не повече от два пъти е

[tex](1+x+x^2)(1+x^2+x^4)(1+x^3+x^6)\cdots=\prod_{k=1}^{\infty}(1+x^k+x^{2k})[/tex]

т.е. като се умножи и развие в ред, коефициента пред [tex]x^n[/tex] дава търсения брой за числото [tex]n[/tex].

Тази фунция може да се запише като

[tex]\prod_{k=1}^{\infty}\frac{1-x^{3k}}{1-x^k}[/tex]

Пораждащата фунция за брой на начините по които може да се представи дадено естествено число като сума на естествени без кратни на три е

[tex]\prod\frac{1}{1-x^k}[/tex]

като произведението е само по тези к, които не са кратни на три. Може да я запишем по следния начин

[tex]\frac{\prod_{k=1}^{\infty}\frac{1}{1-x^k}}{\prod_{k=1}^{\infty}\frac{1}{1-x^{3k}}}=\prod_{k=1}^{\infty}\frac{1-x^{3k}}{1-x^k}[/tex]

Не ми се пише подробно, дано това е достатъчно ясно.

[drago]

Ясно е, но за съжаление не е вярно. Нито за първат хар. ф-я, нито за втората.
За първата: ами напр. коефициента пред x^5-та няма как да "хване" представянето 5=1+1+3, защото няма как два x^1 да умножиш 1 едно x^3. Същото е за 5=2+2+1.
За втората:сам може да видиш, че тази хар. ф-я "хваща" и представяния, в които има членове кратни на 3.
Според мен ще е трудничко да изолират точно тези представяния с този подход!?

[rashi101]

Мартин е абсолютно прав. Всяко [tex]x^{2k}[/tex] от първата функция всъщност е за вариантите, когато това число се използва два пъти. Така за [tex]1+1+3=5[/tex] ще вземеш [tex]x^2[/tex] от първите скоби и [tex]x^3[/tex]. Втората функция също е вярна, помисли и ще видиш. Задачата е от любимата ми книга, The Art and Craft of Problem Solving.
Трябва още малко да си поблъскам главата върху решението на Драго, математиката, изучавана извън училище, все още е нещо ново за мен. Ако обаче отделиш време да ми обясниш по-подробно решението си, ще съм адски благодарна.

[drago]

Сори, но не е така.
x^2 и x^3 формират предствянето 5=2+3, това не е същото като 5=1+1+3, нали! Не е само 5. Представяне от вида n=n1+n1+..., където n1 е нечетно няма как да се хванат от тази ф-я. И втората хар. ф-я не е това, което трябва.
Тук оставям настрана разни прозаични въпроси за сходимостта на тези произведения, които също изискват обосновка при тези подходи.

[rashi101]

Напротив, точно така си е. Да разгледаме представянията [tex]n=k+k+...[/tex] и [tex]n=2k+...[/tex]. Функцията отчита и двете. Първото се получава, когато вземеш [tex]x^{2k}[/tex] от [tex](1+x^k+x^{2k})[/tex], а второто - когато вземеш [tex]x^{2k}[/tex] от [tex](1+x^{2k}+x^{4k})[/tex].

По същия начин се разсъждава и за втората функция. Тя е:

[tex](1+x+x^2+x^3+\dots)(1+x^2+x^4+x^6+\dots)(1+x^4+x^8+x^{12}+\dots)\dots=\\\frac{(1+x+x^2+x^3+\dots)(1+x^2+x^4+x^6+\dots)(1+x^3+x^6+x^9+\dots)\dots}{(1+x^3+x^6+x^9+\dots)(1+x^6+x^{12}+x^{18}+\dots)(1+x^9+x^{18}+x^{27}+\dots)\dots}=\prod_{k=1}^{\infty}\frac{1-x^{3k}}{1-x^k}[/tex]

Последното равенство е вярно, тъй като става дума за безброй суми на геометрични прогресии.

Остави решението на Мартин, дай да помислим за твоето, че доста се чудих и признавам, че не го разбирам добре. По точно, може ли да ми обясниш тази част:

Ako {x1,...,xs, 3^k1.y1,...,3^km.ym}e oт Y2 (x1,...,xs,y1,...,ym не се делят на 3, а измежду x1,...,xs няма някое което се повтаря повече от 2 пъти.) Съпоставяме: {x1,...xs, y1,...(3^k1 пъти), ..., ym(3^km пути) }. то е от Y1.

Мерси предварително.

[drago]

Уау!.., изглежда че е така и тези представяния наистина могат де се "охарактеризират". Първата хар. ф-я със сигурност парави каквото трябва.
Май в последните 2 поста изговорих един куп глупости, за което се извинявам, ако съм засегнал някой- направил съм го единствено от простотия- плъзнах поглед и реших, че не става
Относно другото решение: Ако си представяш представянияята на N като сума, като множества от етстествени числа, с повтарящи се елементи... или по-коректно като множество от наредени двойки: {<a,b>,...} , b показва колко пъти a се повтаря в представянето; та на всяко такова множество, в което има: а, което се дели на 3 и няма b>=3 съпоствяме друго множество по следния начин: всяко <3^к.a,b>(k>=1, 3 не дели a и b<=2) подменяме с <a, 3^k.b> и получаваме ново представяне, което няма елемент делящ се на три, но има поне една тройка повт. се елементи. В термините на първия ми пост това е съответствие Y2 ->Y1. При това взаимно еднозначно,.. е последното трябва да се покаже. Ако има още нещо неясно питай!
Поздрави!

[drago]

Още нещо. Интересно ми е как е решена задачата/ако е/ в The Аrt and Craft of Problem Solving. Не ми се рови да търся. Ще съм благодарен ако ми кажеш.
Иначе благодаря за задачата и дискусията. Задачата е просто един бисер... простичко формулирана, обаче...и така.

[allier]

Най-вероятно е решена с генерираща функция, както martin.nikolov е показал. Това си е най-стандартният начин.

[rashi101]

Да, точно така е. Всъщност, в книгата е решена с пораждащи функции малко по-лесната задача "Да се докаже, че всяко естествено число n може да бъде представено като сбор на различни естествени числа по толкова начини, по колкото - като сбор на нечетни числа", а тази е оставена за упражнение.
Мерси за оригиналното решение, drago - още един метод, за който не ми беше идвало наум