Всяко естествено число има кратно, записано само с 0 и 1

[mdelyakova]

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

[kucheto]

Не се вписвам в графата 7-8 клас, затова ще напиша решението като скрито съобщение:

Скрит текст: покажи

Нека даденото число е [tex]n=2^x5^ym,\ (m,2)=(m,5)=1.[/tex] Нека кратното му е [tex]a.[/tex] Ясно е, че [tex]a[/tex] ще завършва с [tex]max(x,y)[/tex] нули, т.е. достатъчно е да търсим число [tex]b[/tex], делящо се на [tex]m.[/tex] За целта да разгледаме числата, състоящи се само от единици, нека k-тото число да бележим с [tex]C_k.[/tex] Съгласно принципа на Дирихле измежду числата [tex]C_1,C_2,...,C_{m+1}[/tex] ще има две, които дават един и същ остатък при деление на [tex]m.[/tex] Нека това са [tex]C_i,C_j,\ 1\le i<j\le m+1\Rightarrow m|C_i-C_j=10^jC_{i-j}\Rightarrow m|C_{i-j}.[/tex] Но [tex]b=C_{i-j}\Rightarrow a=10^{max(x,y)}b[/tex] изпълнява условието, с което задачата е решена.

[Гост1]

Тук или директно, но не просто, Теоремата на Ойлер.

[drago]

Не се вписвам в графата 7-8 клас, затова ще напиша решението като скрито съобщение:

Скрит текст: покажи

Нека даденото число е [tex]n=2^x5^ym,\ (m,2)=(m,5)=1.[/tex] Нека кратното му е [tex]a.[/tex] Ясно е, че [tex]a[/tex] ще завършва с [tex]max(x,y)[/tex] нули, т.е. достатъчно е да търсим число [tex]b[/tex], делящо се на [tex]m.[/tex] За целта да разгледаме числата, състоящи се само от единици, нека k-тото число да бележим с [tex]C_k.[/tex] Съгласно принципа на Дирихле измежду числата [tex]C_1,C_2,...,C_{m+1}[/tex] ще има две, които дават един и същ остатък при деление на [tex]m.[/tex] Нека това са [tex]C_i,C_j,\ 1\le i<j\le m+1\Rightarrow m|C_i-C_j=10^jC_{i-j}\Rightarrow m|C_{i-j}.[/tex] Но [tex]b=C_{i-j}\Rightarrow a=10^{max(x,y)}b[/tex] изпълнява условието, с което задачата е решена.

Елегантно решение!
А защо в началото е тази увертюра с отделянето на [tex]m[/tex] взаимно просто с 10 ? Направо тръгвай с принципа на Дирихле за остатъците на 111...1 по модул [tex]n[/tex].

[Гост1]

Решението наистина е елетантно. Подобна задача с подобно решение е следната:
На дъската е написано естествено число. На всяка стъпка отдясно към него се дописва цифра различна от 9. Да се докаже, че след краен брой стъпки на дъската ще се появи съставно число.
Тя отново може да се реши и с теоремата на Ойлер.

[kucheto]

Решението наистина е елетантно. Подобна задача с подобно решение е следната:
На дъската е написано естествено число. На всяка стъпка отдясно към него се дописва цифра различна от 9. Да се докаже, че след краен брой стъпки на дъската ще се появи съставно число.
Тя отново може да се реши и с теоремата на Ойлер.

ЗМС 2009, 9.4.
Споменът от точно тази задача използвах за решението си.