Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Udowodnić, że każdą liczbę naturalną \(\displaystyle{ n}\) można przedstawić w postaci sumy takich liczb postaci \(\displaystyle{ 2 ^{i}3 ^{j}}\), że żadna z nich nie jest dzielnikiem którejś z pozostałych.
Zrobimy indukcję ze względu na \(\displaystyle{ n}\).
W ramach pierwszego kroku sprawdzamy wszystko do \(\displaystyle{ n=8}\). Wszystko działa w w miarę oczywisty sposób.
Teraz zakładamy, że wszystkie liczby od \(\displaystyle{ 1}\)do \(\displaystyle{ n-1}\) da się przedstawić w ten sposób.
Zauważmy, że jeśli \(\displaystyle{ 2}\) lub \(\displaystyle{ 3}\) dzieli nam naszą liczbę, to teza zachodzi, bo możemy ją przedstawić w postaci \(\displaystyle{ n=2^{i}3^{j}k}\), a \(\displaystyle{ k<n}\), więc z założenia indukcyjnego da się tak przedstawić, a skoro żaden ze składników w sumie równej \(\displaystyle{ k}\) nie dzieli żadnego innego, to oznacza, że jeśli podzielimy jakiś składnik \(\displaystyle{ 2^{a_{x}}3^{b_{y}}}\) przez jakiś inny, to uzyskamy liczbę niecałkowitą. Jeżeli natomiast pomnożymy obie te liczby przez \(\displaystyle{ 2^{i}3^{j}}\), to przy dzieleniu nam się ten czynnik skróci i i tak liczba nie będzie całkowita.
Zakładamy zatem, że ani \(\displaystyle{ 2}\), ani \(\displaystyle{ 3}\) nie dzieli \(\displaystyle{ n}\).
Niech \(\displaystyle{ 2^{m} < n < 2^{m+1}}\). Ostra nierówność, bo nasza liczba nie jest nawet parzysta. Jako że sprawdziliśmy wystarczająco dużo przypadków początkowych, możemy założyć \(\displaystyle{ m>2}\).
Ponieważ \(\displaystyle{ n}\) nie jest podzielne przez \(\displaystyle{ 3}\), zachodzi:
\(\displaystyle{ n \equiv 2^{m} ( \mod 3)}\) lub \(\displaystyle{ n \equiv 2^{m-1} ( \mod 3)}\).
Bo potęgi dwójki przyjmują na zmianę dwie reszty modulo \(\displaystyle{ 3}\).
Możemy więc zapisać:
W pierwszym przypadku: \(\displaystyle{ n=3k+2^{m}}\)
W drugim: \(\displaystyle{ n= 3k+ 2^{m-1}}\).
Oczywiście na mocy założenia indukcyjnego \(\displaystyle{ k}\) możemy przedstawić w żądanej postaci. Wystarczy teraz udowodnić, że w żadnym przypadku żaden ze składników występujących w sumie \(\displaystyle{ 3k}\) nie dzieli odpowiedniej potęgi dwójki, i vice versa - potęga dwójki nie dzieli żadnego z tych składników.
Pierwsze zadanie jest prostsze - oczywiście każdy z tych składników podzielny jest przez \(\displaystyle{ 3}\) stojące przed \(\displaystyle{ k}\), więc nie może dzielić potęgi dwójki.
Weźmy drugi przypadek i przypuśćmy teraz, że istnieje taki składnik w sumie \(\displaystyle{ 3k}\), który jest podzielny przez \(\displaystyle{ 2^{m-1}}\). Ponieważ \(\displaystyle{ \nwd(3, 2^{m-1}) = 1}\), taki składnik musi występować w sumie \(\displaystyle{ k}\). W związku z tym: \(\displaystyle{ n=3(l+q2^{m-1}) + 2^{m-1}> (3q+1)2^{m-1} > 4 \cdot 2^{m-1} = 2^{m+1}}\)
Otrzymaliśmy \(\displaystyle{ n>2^{m+1}}\), co stoi w sprzeczności z definicją \(\displaystyle{ m}\).
W pierwszym przypadku rozumowanie jest analogiczne.
Oznacza to, że udowodniliśmy drugi krok indukcyjny, a zatem na mocy indukcji matematycznej teza jest prawdziwa, co kończy dowód.
