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.
W jednej z kategorii na tegorocznym Kangurze, pojawił się taki o to problem:
Ile liczb całkowitych dodatnich będących wielokrotnościami liczby \(\displaystyle{ 2013}\) ma dokładnie \(\displaystyle{ 2013}\) różnych dodatnich dzielników (do dzielników liczby zaliczamy \(\displaystyle{ 1}\) i tę liczbę)?
Otóż ja podbijam i stawiam ogólniejszy problem:
Dana jest liczba naturalna \(\displaystyle{ n > 1}\), oraz jej rozkład na czynniki pierwsze \(\displaystyle{ n= \prod_{i=1}^{m}p_{i}^{\alpha_{i}}}\). Ile liczb całkowitych dodatnich będących wielokrotnościami liczby \(\displaystyle{ n}\) ma dokładnie \(\displaystyle{ n}\) różnych dodatnich dzielników?
Ukryta treść:
Problem łatwo rozstrzygnąć w przypadku podobnym do oryginalnego, to jest gdy \(\displaystyle{ \alpha_{1}=\alpha_{2}= \ldots = \alpha_{m}=1}\).
Problem łatwo rozstrzygnąć w przypadku podobnym do oryginalnego, to jest gdy \(\displaystyle{ \alpha_{1}=\alpha_{2}= \ldots = \alpha_{m}=1.}\)
tak jak np \(\displaystyle{ n=2013=3 \cdot 11 \cdot 61}\) tj. dla liczb bezkwadratowych ;wielokrotność n to \(\displaystyle{ 3^{\alpha}11^{\beta}33^{\gamma}}\)
oraz te wykładniki powiekszone o 1 sa elementami zbioru \(\displaystyle{ \{3, 11, 61\}}\) co da skończona ilosc rozwiazan.
Jesli \(\displaystyle{ n}\) nie jest bezkwadratową, (tj. ma dzielnik \(\displaystyle{ p^2}\), gdzie \(\displaystyle{ p}\) jest lizcbą pierwsza)to na ogół bedzie nieskończona ilość rozwiązań, np. gdy \(\displaystyle{ n=p^2q}\) to liczby \(\displaystyle{ p^{p-1}q^{p-1}r^{q-1}}\) , gdzie r jest liczbą pierwsza maja \(\displaystyle{ n}\) dzielników, itd.
z łatwością można też opisać klasę liczb postaci \(\displaystyle{ n=a^{\alpha}}\), gdzie \(\displaystyle{ 1<a \in \mathbb{N}}\)
Załóżmy, że \(\displaystyle{ k=a^{\beta}}\) i niech \(\displaystyle{ m}\) będzie wielokrotnością \(\displaystyle{ n}\) taką że
\(\displaystyle{ m=kn=a^{\alpha+\beta}}\)
wówczas oznaczając przez \(\displaystyle{ \theta (n)}\) liczbę dzielników liczby \(\displaystyle{ n}\) mamy
\(\displaystyle{ n= \prod_{i=1}^mp_{i}^ {\alpha_1}}\) wielokrotność tej liczby jest pomnożona przez \(\displaystyle{ q^{\beta_0}\prod_{i=1}^mp_{i}^{ \beta_{i}}}\), gdzie \(\displaystyle{ q}\) to liczba pierwsza różna od \(\displaystyle{ p_{i}}\). Ilość dzielników wielokrotności wynosi \(\displaystyle{ (\beta_0+1)(\alpha_1+\beta_1+1)(\alpha_2+\beta_2+1)...(\alpha_m+\beta_m+1)}\)
Zauważmy, że \(\displaystyle{ p_{i}^{ \alpha_{i}} \ge \alpha_i+1}\)(to się udowadnia łatwo z indukcji).
Jeśli istnieje jakieś \(\displaystyle{ p_i}\), że \(\displaystyle{ p_i^{\alpha_i-1} \ge \alpha_i+1}\). To liczba możliwych wielokrotności jest nieskończona, bo wystarczy wziąć \(\displaystyle{ \beta_0=p_i-1 \ \beta_i= p_i^{\alpha_i-1} - \alpha_i-1}\) pozostałe \(\displaystyle{ \beta_j = p_{j}^{ \alpha_{j}}- \alpha_j-1}\). Warunek \(\displaystyle{ p^{\alpha -1} \ge \alpha +1}\) Zachodzi:
dla \(\displaystyle{ p=2}\),gdy \(\displaystyle{ \alpha \ge 3}\)
dla \(\displaystyle{ p \ge 3}\) , gdy \(\displaystyle{ \alpha \ge 2}\)
Co daje dwa przypadki do rozpatrzenia:
1) wszystkie liczby pierwsze są w wykładniku \(\displaystyle{ 1}\). \(\displaystyle{ \alpha_1=\alpha_2=...=\alpha_m=1}\) liczba dzielników wynosi \(\displaystyle{ (\beta_0+1)(2+\beta_1)(2+ \beta_2)...(2+ \beta_m)}\) To ma się równać \(\displaystyle{ n}\), które jest, co najwyżej iloczynem \(\displaystyle{ m}\) różnych liczb pierwszych. Oznacza to , że \(\displaystyle{ \beta_0=0}\) , bo liczba dzielników musi być iloczynem co najwyżej \(\displaystyle{ m}\) liczb większych od \(\displaystyle{ 1}\)( ,a \(\displaystyle{ (2+\beta_1)...(2+\beta_m)}\) już takie jest ). Z tego wynika również ,że \(\displaystyle{ 2+\beta_i}\) musi być którąś z liczb pierwszych \(\displaystyle{ p_1,...,p_m}\). Co daje \(\displaystyle{ n!}\) możliwości i tyle samo wielokrotności.
2)liczba \(\displaystyle{ n}\) jest podzielna przez \(\displaystyle{ 4}\) (\(\displaystyle{ p_1=2 \ \alpha_1=2}\) ) i pozostałe liczby pierwsze są w pierwszej potędze. \(\displaystyle{ n=4p_2p_3...p_m}\) Jeśli \(\displaystyle{ m \neq 1}\) , to liczba dzielników jest nieskończona, bo wystarczy wziąć \(\displaystyle{ \beta_0=1 \ \beta_1=p_1-1 \ \beta_2=1}\) a pozostałe \(\displaystyle{ \beta_j=p_j^{ \alpha_j}-\alpha_j-1}\).
Pozostaje mały przypadek, gdy \(\displaystyle{ n=4}\) dla niego jest tylko jedna wielokrotność. \(\displaystyle{ 8}\)
