Olimpiada Matematyczna gość: Witam. Ostatnio rozwiązywałem zadanie 3 z II etapu OM (link: https://om.mimuw.edu.pl/static/app_main/problems/om63_2r.pdf), lecz moje rozwiązanie nie pokrywa się z rozwiązaniem organizatorów. Czy mógłbym prosić o jego weryfikację i ocenę punktową wg skali olimpijskiej? Oczywiście bez pośpiechu, to tylko rozrywka. Załóżmy nie wprost, że istnieje zbiór m+1 liczb niespełniający tezy zadania− nazwijmy go A. Niech zbiór dzielników pierwszych (z rozkładu) x−tej liczby tego zbioru będzie oznaczany przez X_x, zaś zbiór dzielników iloczynu pozostałych−przez Y_x. Wówczas zauważmy, że istnieje taka liczba pierwsza, która więcej razy powtarza się jako element w zbiorze X_x niż Y_x− gdyby było inaczej, zbiór Y_x zawierałby wszystkie elementy zbioru X_x, co przeczyłoby założeniu. Weźmy jedną z takich liczb i nazwijmy go p_x. Weźmy liczbę całkowitą y∊A. Przyjmijmy, że zachodzi warunek p_y=p_x. Niech zbiór [a₁, a₂, a₃, ..., a_n] oznacza liczbę elementów wynoszących p_x w danym zbiorze. Wiemy, że (∑a_i)−a_y<a_y⋀ (∑a_i)−a_x<a_x ⇒a_x<a_y⋀a_y<a_x−sprzeczność. To wszystko oznacza , że liczby pierwsze [p₁, p₂, ..., p₃, p₍m+1)] są dzielnikami pierwszymi liczb należących do zbioru (1,2,...,n) oraz są różne. Jest to sprzeczne z informacją w treści zadania, która mówi, że tych liczb jest tylko m. Otrzymana sprzeczność kończy rozwiązanie zadania. Mogą być drobne literówki z powodu zmęczenia − z góry przepraszam. Generalnie chodzi mi o ocenę samego toku rozumowania.

Adamm: error 404

gość: Gdzie?

Adamm: Zbiory mają tą własność, że ich elementy się nie powtarzają. Więc nie rozumiem tej części: "Wówczas zauważmy, że istnieje taka liczba pierwsza, która więcej razy powtarza się jako element w zbiorze X_x niż Y_x"

Adamm: "Niech zbiór [a₁, a₂, a₃, ..., a_n] oznacza liczbę elementów wynoszących p_x w danym zbiorze." Co to znaczy, że zbiór oznacza liczbę elementów wynoszących p_x w danym zbiorze?

gość: Zaznaczyłem wcześniej, że chodzi mi o zbiór czynników z rozkładu na czynniki pierwsze. Skoro to nie zbiór, zamieńmy ten termin na grupa. Niestety, moja wiedza z logiki ma duże luki −zawsze myślałem, że zbiór to po prostu tablica wartości −jak w informatyce.

Adamm: rozumiem że chodzi o np. 20 = 2²*5, i X₂₀ = {2², 5} ? A przez powtarzanie się, mamy na myśli potęgę? Np. 2 powtarza się 2 razy, bo 2²∊X₂₀ ?

gość: p_x jest liczbą, która występuje w grupie z rozkładu liczniej niż w grupie z rozkładu pozostałych liczb. Zliczamy wystąpienia tej liczby w pozostałych grupach i tworzymy nową tablicę wystąpień [a₁,a₂,...,a_n].

gość: Oczywiście chodzi o potęgę.

gość: Przepraszam za moją ignorancję. Logiki jeszcze nie miałem, po prostu wpadłem na pomysł i zastanawiałem się, czy jest dobry.

Adamm: No dobra. Rozumiem to pewnego momentu. Wyjaśnij ten zapis [a₁, a₂, a₃, ..., a_n] Dlaczego od 1 do n? Zliczamy potęgi p_x w zbiorach X_y, gdzie y przebiega zbiór A? Nie powinien to być wektor o m+1 lub m elementach? [a₁, ..., a_m] ?

gość: Literówka. Chodziło właśnie o to.

Adamm: Ale potem oznaczasz to inaczej. Chodzi tu raczej o odwzorowanie y→a_y, gdzie a_y to potęga z jaką p_x występuje w X_y.

gość: Dokładnie.

Adamm: Dalej, zakładamy że p_x występuje z większą potęgą w X_y niż w Y_y. Otrzymujemy sprzeczność. Przypisując każdej liczbie x∊A jej odpowiednią liczbę pierwszą p_x, widzimy że p_x≠p_y gdy x≠y, więc mamy m+1 liczb pierwszych w {1, ..., n} sprzeczność Dowód niezbyt formalny, chociaż sensowny, i po dość dużych reformacjach mógłby być zrozumiały.

Adamm: Poza tym błędów nie widzę, a na olimpiadach się nie znam, więc nie ocenię.

gość: Dziękuję bardzo. Pierwszy raz w życiu "rozwiązałem" zadanie z Olimpiady Matematycznej. Dziwi mnie, że w rozwiązaniu ze strony użyto bardziej skomplikowanej metody−ta wydaje się najprostsza.