домашно с индукция

[petrovd]

Задачата е следната:
Представете си наличието на марки от 5 пенса и 7 пенса, неограничен брой.Кое е най-малкото число Z принадлежащо на N, такова че за всички к >= Z можем да направим всички комбинации от к пенса като иползваме само трите марки (5,7 и неизвестната).Докажете твърдението с индукция.

Благодаря предварително!

[Knowledge Greedy]

Да разгледаме всички естествени числа от вида [tex]5x+7y[/tex], където [tex]x[/tex] и [tex]y[/tex] са цели неотрицателни.
Първо ще отговорим на въпроса: "Кое е най-голямото естествено число [tex]z[/tex], за което уравнението [tex]5x+7y=z[/tex] няма решения в естествени числа?".
Отговорът е [tex]z=23[/tex]
Ако то имаше решение, то едно от уравненията [tex]7y=23;\,\ 7y=18; \,\ 7y=13; \,\ 7y=8[/tex] щеше да има естествен корен.
По-нататък описваме представянията на последователните естествени числа
(Това представлява базата на МПМИ).
[tex]2.5+2.7=24[/tex]
[tex]5.5=25[/tex]
[tex]5+3.7=26[/tex]
[tex]4.5+7=27[/tex]
[tex]4.7=28[/tex]
[tex]3.5+2.7=29[/tex]
[tex]6.5=30[/tex]
[tex]2.5+3.7=31[/tex]
[tex]5.5+7=32[/tex]
[tex]5+4.7=33[/tex]
[tex]4.5+2.7=34[/tex]
[tex]5.7=35[/tex]
[tex]3.5+3.7=36[/tex]
[tex]6.5+7=37[/tex]
[tex]2.5+4.7=38[/tex]
[tex]5.5+2.7=39[/tex]
[tex]8.5=40[/tex]
[tex]4.5+3.7=41[/tex]
[tex]7.5+7=42[/tex]
[tex]3.5+4.7=43[/tex]
Последното може да се представи като [tex]4.5+23=43[/tex] и ето защо всяко естествено число [tex]k\ge 23[/tex]
може да се представи като естествена линейна комбинация на [tex]5[/tex], [tex]7[/tex] и [tex]23[/tex], т.е. във вида .
[tex]k=5x+7y+23t[/tex].
Доказателството на последното твърдение формално може да се завърши с втората част - индуктивния преход на МПМИ (Метода на пълната математическа индукция).

[pal702004]

Това с третия номинал нещо не ми е ясно какъв му е смисъла.

Кое е най-малкото число Z принадлежащо на N, такова че за всички к >= Z можем да направим всички комбинации от к пенса като иползваме само трите марки (5,7 и неизвестната)

Ами [tex]Z=1[/tex] е най-малкото такова естествено число Ако въпроса беше "кое е най-голямото естествено число, непредставимо във вид [tex]5x+7y[/tex], където [tex]x,y[/tex] са цели неотрицателни числа", то отговорът е, както каза Knowledge Greedy е 23. Тоест, при [tex]k>23[/tex] този трети номинал въобще не ни трябва.
По простичкият начин: ако [tex]k[/tex] е представимо, то и [tex]k+5[/tex] е представимо и е достатъчно да намерим 5 последователни естествени числа, представими в такъв вид. (от 24 нататък).
По-тарикатският: ако [tex]k>22[/tex] е представимо, то и [tex]k+1[/tex] (а следователно и всички естествени по-големи от [tex]k[/tex]) също е представимо:
[tex]k=5x+7y[/tex]

[tex]k+1=5(x-4)+7(y+3)[/tex]
а също така
[tex]k+1=5(x+3)+7(y-2)[/tex]

И тъй като [tex]k>22[/tex], то в представянето на [tex]k[/tex] има поне 2 монети с номинал 7, или поне 4 монети с номинал 5, то поне едното от двете представяния за [tex]k+1[/tex] е възможно.

[Knowledge Greedy]

Може би е направен твърде буквален превод и на нашия език настъпва някакво объркване.