Delta mi!

Jeżeli jest liczbą parzystą, to żądanym przedstawieniem jest

Przypuśćmy, że jest liczbą nieparzystą i niech będzie najmniejszą nieparzystą liczbą pierwszą, która nie jest dzielnikiem liczby Wówczas przedstawienie liczby w postaci różnicy

spełnia warunki zadania. Rzeczywiście, każda z liczb oraz ma dokładnie te dzielniki pierwsze co liczba a ponadto po jednym dodatkowym - odpowiednio oraz

Rozważmy dowolny podział zbioru dodatnich liczb całkowitych spełniający zadane warunki. Zauważmy, że jeżeli to dla dowolnego mamy co jest sprzeczne z założeniem, że zbiory i są rozłączne. Wobec tego

Oznaczmy przez najmniejszy element zbioru Korzystając z pierwszego z danych warunków, łatwo indukcyjnie udowodnić, że dla każdej dodatniej liczby całkowitej :

skąd wniosek, że wszystkie liczby niepodzielne przez należą do zbioru W szczególności z drugiego z danych warunków wynika, że każda liczba podzielna przez ale niepodzielna przez należy do zbioru

Przypuśćmy, że dla pewnej dodatniej liczby całkowitej Wówczas, skoro to co jest sprzeczne z konkluzją poprzedniego akapitu. To oznacza, że wszystkie liczby podzielne przez należą do zbioru

Pozostaje zauważyć, że dla każdego jeżeli jest zbiorem liczb niepodzielnych przez a - zbiorem liczb podzielnych przez to warunki zadania są spełnione.

Oznaczmy przez największy wspólny dzielnik liczb i Ponieważ liczby i są względnie pierwsze, a ich suma jest podzielna przez więc liczba jest względnie pierwsza z liczbami i Ponadto liczba jest podzielna przez Stąd wynika, że czyli

Niech będzie dodatnią liczbą całkowitą. Zauważmy, że każda mniejsza od wielokrotność liczby

jest podzielna przez sumę swoich cyfr. Rzeczywiście, suma cyfr każdej takiej liczby jest nie większa od i podzielna przez więc jest dzielnikiem liczby a tym bardziej dowolnej jej wielokrotności.

Wystarczy więc udowodnić, że dla każdego można dobrać takie aby spełniona była nierówność

a szukany ciąg arytmetyczny będą wówczas tworzyły liczby dla

Zauważmy, że każda liczba pierwsza wchodzi do rozkładu liczby na czynniki pierwsze z wykładnikiem a zatem nie większym od Wobec tego

gdzie mnożenie przebiega liczby pierwsze oraz skorzystaliśmy z nierówności zasugerowanej we wskazówce do zadania (prawdziwej dla gdzie jest pewną dodatnią liczbą całkowitą).

Ponieważ więc dla pewnej dodatniej liczby całkowitej Do zakończenia rozwiązania wystarczy przyjąć

Udowodnimy, że wszystkie liczby pomalowano tym samym kolorem.

Przyjmijmy oznaczenie jeżeli oraz niech Zauważmy, że dla każdego liczba

jest podzielna przez a zatem Ponadto, dla każdego liczba

jest podzielna przez skąd wniosek, że Wobec tego dla dowolnych liczb całkowitych otrzymujemy

co oznacza, że liczby i pomalowano tym samym kolorem.

Teza zadania: (mod ) - po wprowadzeniu określenia liczby i dodaniu stronami jedynki - ma postać

Liczba jest pierwsza, więc zachodzi dla (małe twierdzenie Fermata). Dalej indukcja: przyjmijmy słuszność dla pewnego ; istnieje zatem liczba dla której Odejmujemy stronami jedynkę i mamy Z określenia wynika ponadto, że (mod ). Tak więc

Uzyskaliśmy zależność z zastąpionym przez To kończy dowód indukcyjny.

Rozważmy wielomian Wówczas liczba jest pierwiastkiem wielomianu Niech Wówczas po przemnożeniu obu stron równości przez otrzymujemy

Stąd liczba jest podzielna przez Ponieważ liczby i są względnie pierwsze, to wiemy, że dzieli liczbę

Zapiszmy liczbę w postaci ( całkowite, nieparzyste). Znajdujemy wykładnik dla którego

(1)

Jeśli pewien wykładnik spełnia ten warunek, to jego dwukrotność też. Można więc wybrać tak, by

(2)

Liczbę o jaką pyta zadanie, spróbujemy znaleźć wśród liczb postaci ( całkowite). Dla różnica

będzie podzielna przez jeśli tylko bowiem czynnik w nawiasie dzieli się przez (por. (1)). Biorąc jeszcze pod uwagę wymaganie, by widzimy, że wystarczy znaleźć liczbę spełniającą nierówność

(3)

wówczas liczba spełni wszystkie żądane warunki.

Gdy jest liczbą nieparzystą, czyli gdy można wziąć (por. (2)).

Gdy jest liczbą parzystą (więc ), warunki (3) postulują istnienie wielokrotności liczby w przedziale Do tego wystarcza, by nie przekraczała wartości (bo tyle jest liczb całkowitych w tym przedziale); a dzięki oszacowaniu (2) wystarczy, by zachodziła nierówność

czyli (równoważnie)

To kończy rozwiązanie, bowiem ostatnia nierówność jest słuszna dla każdej pary liczb całkowitych

Wśród liczb dziesięciocyfrowych jest

wielokrotności liczby Podzielmy je na grupy - w jednej grupie znajdą się liczby złożone z jednakowych cyfr.

Grupy odpowiadają rozwiązaniom równania w liczbach naturalnych - liczby można zinterpretować jako liczby wystąpień cyfry w każdym elemencie danej grupy. Rozwiązań takiego równania jest

Z zasady szufladkowej Dirichleta co najmniej jedna grupa zawiera co najmniej

elementów.

Każdą liczbę naturalną można przedstawić w postaci dla na co najwyżej jeden sposób. Stąd szukamy liczby takich par dla których liczba jest podzielna przez Jest to równoważne podzielności przez

Ponieważ daje z dzielenia przez resztę lub dla dającego z dzielenia przez odpowiednio resztę lub to otrzymujemy równoważność warunku z zadania z podzielnością liczby przez W takim razie liczby i muszą dawać taką samą resztę z dzielenia przez

Podzielmy liczby naturalne od do na sześć podzbiorów ze względu na resztę z dzielenia przez (każdy zawierający elementów). Aby wybrać liczby i wybieramy jeden z podzbiorów, a z niego dwa elementy. Stąd szukana w zadaniu liczba to

Prawa strona podanej równości ma postać ilorazu (licznik to iloczyn ośmiu czynników, mianownik to iloczyn siedmiu czynników). Lewa strona to Wystarczy pokazać, że dowolna liczba pierwsza wchodzi do rozkładów liczb oraz w jednakowej potędze (być może zerowej).

Ustalmy więc liczbę pierwszą i przyjmijmy, że liczby są podzielne odpowiednio przez ale nie przez Wówczas

Należy wykazać, że

Wobec symetrii rozważanych wyrażeń (względem permutacji ) nie tracimy ogólności zakładając, że Napisane równości uzyskują postać

teza gotowa.

(a)

Na przykład, każda para postaci gdzie jest nieparzystą liczbą pierwszą, ma wymaganą własność, bowiem

(b)

Przypuśćmy, że para liczb względnie pierwszych spełnia podane równanie: Skoro liczby są względnie pierwsze, wynika stąd, że jest dzielnikiem liczby Wobec tego Taka nierówność zajść może (w formie równości) tylko wtedy, gdy każda liczba ze zbioru jest dzielnikiem liczby W szczególności musi dzielić się przez To zaś ma miejsce jedynie dla (rozważamy, z założenia, tylko ).

Role liczb są symetryczne; to samo rozumowanie pokazuje, że także ; sprzeczność z założeniem, że są względnie pierwsze. Nie istnieje więc para, o jakiej mowa w pytaniu (b).

Ponieważ to iloczyn wszystkich wyrazów ciągu nie zmienia się po wykonaniu ruchu. W szczególności każdy z wyrazów ciągu jest ograniczony z góry przez i ograniczony z dołu przez Ponadto w każdym ruchu, modyfikującym pewne wyrazy o indeksach liczba jest zamieniana na większą liczba zaś - na mniejszą Żaden wyraz ciągu nie może być nieskończenie wiele razy zmniejszany (jako ograniczony z dołu przez ) ani zwiększany (jako ograniczony z góry przez ). W takim razie każdy wyraz zostanie zmieniony skończenie wiele razy, czyli nie możemy wykonać nieskończenie wielu ruchów.

Istnieją takie ciągi. Jedna z możliwych konstrukcji:

Przyjmujemy Będziemy przedłużać zdefiniowany odcinek ciągu, dołączając po dwa wyrazy.

Ustalmy liczbę parzystą i przyjmijmy, że wyrazy są już określone. Najmniejsza dodatnia liczba całkowita, różna od będzie wyrazem (to gwarantuje, że w budowanym ciągu znajdą się wszystkie liczby całkowite dodatnie).

Określamy wyraz wzorem

gdzie jest liczbą całkowitą tak dobraną, by uzyskana liczba była dodatnia oraz różna od liczb i różna od (powstający ciąg będzie więc miał wszystkie wyrazy różne). Przy tym

Wymagane warunki podzielności są spełnione. Indukcyjnie powstaje ciąg nieskończony jakiego szukamy.

Liczba dzieli się przez więc i przez Wobec nieparzystości liczba dzieli się przez więc i przez Zatem suma tych dwóch liczb, czyli dzieli się przez Z symetrii warunków zadania wynika, że dzieli się także przez W takim razie dzieli się przez liczbę

Tak, dla każdej funkcji łatwo wskazać funkcję o wymaganych własnościach. Niech będzie rosnącym ciągiem wszystkich potęg liczb pierwszych:

Funkcja (o własności gdy ) jest wyznaczona przez ciąg wartości ; zaś podany warunek multyplikatywności nie stawia na owe wartości żadnych ograniczeń. Wobec tego konstruujemy taki ciąg indukcyjnie. Niech będzie dowolną liczbą naturalną większą od

Załóżmy, że liczby …, zostały już określone. Patrzymy na zbiór wszystkich liczb postaci gdzie jest iloczynem różnych liczb ze zbioru Określamy jako dowolną liczbę naturalną większą od wszystkich takich liczb

Wybrany ciąg wartości wraz z warunkiem multyplikatywności, jednoznacznie generuje funkcję Spełnia ona także pozostały z zadanych warunków; jeśli bowiem liczba zostanie zapisana jako iloczyn gdzie wówczas

Załóżmy więc, że liczby całkowite i są niepodzielne przez liczbę pierwszą oraz że dla pewnej trójki liczb całkowitych nieujemnych zachodzą równości i (w dalszym ciągu myślę, że zadanie nie jest trudne). Aby wykazać, że iloczyn jest sześcianem pewnej liczby całkowitej, wystarczy przecież wykazać, iż każdy czynnik pierwszy występuje w rozkładzie tej liczby z wykładnikiem podzielnym przez Mamy Mianownik tego ułamka jest podzielny przez liczbę i niepodzielny przez Zastąpienie uporządkowanej trójki liczb trójką lub powoduje, że liczba lub - więc ta z treści zadania - ma być całkowita (trójka to jednak coś innego, bo na ogół ). Można więc założyć, że Mamy

• Jeśli to więc występuje w rozkładzie iloczynu na czynniki pierwsze z wykładnikiem
• Jeśli to i więc dwa z trzech składników licznika dzielą się przez a trzeci nie, co oznacza, że liczba nie jest całkowita, wbrew założeniu.
• Jeśli to i więc znów liczba nie jest całkowita.
• Jeśli to i więc znów liczba nie jest całkowita.
• Jeśli to i to teraz dwa składniki nie dzielą się przez Ich suma może dzielić się przez tylko wtedy, gdy więc w tym wypadku liczba jest podzielna przez

Wykazaliśmy, że jeśli liczba jest całkowita, to liczba pierwsza wchodzi w rozkład liczby na czynniki pierwsze z wykładnikiem podzielnym przez

Wygodnie będzie zacząć od przypadku, gdy losowanie jest ze zwracaniem. Wynik losowania to wówczas para uporządkowana dzielników liczby Zdarzenia identyfikujemy z odpowiednimi podzbiorami zbioru wszystkich takich par. Gdy para należy do liczby są względnie pierwszymi dzielnikami liczby zatem także iloczyn jest dzielnikiem Oczywiście dzieli więc para należy do

Na odwrót, gdy jest dowolną parą ze zbioru (więc ), wtedy iloraz też jest dzielnikiem i to względnie pierwszym z (bo gdyby miały wspólny dzielnik liczba więc i byłaby podzielna przez wbrew założeniu zadania). Zatem para należy do

Opisane operacje są wzajemnie odwrotne. Stąd wynika, że zbiory i są równoliczne; zaś zdarzenia są (przy losowaniu ze zwracaniem) jednakowo prawdopodobne.

Losowanie bez zwracania eliminuje dublety, tzn. pary postaci gdzie W poprzednim modelu, do zbioru należała tylko jedna taka para ; do należały wszystkie. Więcej par zostało wyeliminowanych z wobec czego (przy losowaniu bez zwracania) zdarzenie jest bardziej prawdopodobne niż