[Teoria liczb] suma cyfr

[marcin7Cd]

Udowodnij, że dla każdej liczby całkowitej dodatniej \(\displaystyle{ n}\) istnieje taka liczba \(\displaystyle{ n}\) cyfrowa \(\displaystyle{ x}\), że każda jej cyfra jest niezerowa i \(\displaystyle{ x}\) jest podzielne sumę swoich cyfr.

Wydaje mi się, że jest to ciekawe zadanie i chyba można je rozwiązać na wiele sposobów.

[ElEski]

Ukryta treść:    

suma cyfr \(\displaystyle{ =2^{k}}\)

[a4karo]

Ukryta treść:    

suma cyfr \(\displaystyle{ =2^{k}}\)

Ujawnisz co chciałeś przez to powiedzieć?

[ElEski]

Z wielką chęcią.
Idea jest taka, że jak weźmiemy sobie jakieś \(\displaystyle{ 2^{k} \in (2n,8n)}\), to:
1.) \(\displaystyle{ k<<n}\),
2.) Podzielność liczby jakiejś przez \(\displaystyle{ 2^{k}}\) to tak naprawdę podzielność jej k-cyfrowego suffixu przez \(\displaystyle{ 2^{k}}\)

Więc ustaliwszy \(\displaystyle{ k}\) bierzemy sobie jakiś losowy* suffix k-cyfrowy podzielny przez \(\displaystyle{ 2^{k}}\), a resztę cyfr uzupełniamy tak, żeby nam się suma zgodziła. Uda się to, bo jak uzupełnimy samymi jedynkami, to suma cyfr będzie mniejsza niż \(\displaystyle{ 2^{k}}\), a jak samymi dziewiątkami, to większa.
Oczywiście to się może sypać dla jakichś bardzo małych \(\displaystyle{ n}\),

Ukryta treść:    

ale syfem zajmę się prędzej na IMO, niż na forum

*-ten suffix nie jest tak do końca losowy, bo nie może mieć zer. No ale można zbudować liczbę x-cyfrową z samych 6 i 9 podzielną przez \(\displaystyle{ 2^{x}}\). Jak to jest możliwe? Indukcyjnie, startujemy od samej szóstki i w kroku doklejamy na początek naszej liczby 6 albo 9, zależnie od tego, czy "dzieliła się tez przez wyższą potęgę 2, czy nie"

[a4karo]

Niestety żadne x66 ani x69 nie dzieli się przez 4

[ElEski]

Na szczęście
6 dzieli się przez 2,
96 dzieli się przez 4,
696 dzieli się przez 8,
9696 dzieli się przez 16,
69696 dzieli się przez 32,
669696 dzieli się przez 64.

[a4karo]

Ok, sorry