LIX OM - I -Zadanie 12

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Dana jest liczba całkowita $m \geqslant 2$ . Wyznaczyć najmniejszą taką liczbę całkowitą
$n \geqslant m$ , że dla każdego rozbicia zbioru $\{m,m+1,\dots ,n\}$ na dwa podzbiory, przynajmniej jeden z
tych podzbiorów zawiera takie liczby $a, b, c$ (niekoniecznie różne), że $ab = c$ .

Rozwiązanie

Odpowiedź: $n = m^5$ .

Załóżmy, że istnieje rozbicie zbioru $\{m,m+1,\dots ,m^5\}$ na dwa podzbiory $S$ i $T$ ,
z których żaden nie zawiera dwóch liczb (niekoniecznie różnych) wraz z ich iloczynem. Przypuśćmy przy tym,
że $m \in S$ . Liczba $m^2 = m \cdot m$ jest iloczynem dwóch elementów zbioru $S$ , zatem musimy mieć
$m^2 \in T$ . Stąd zaś $m^4= m^2\cdot m^2 \in S$ . Widzimy, że $m, m^4 \in S$ , co oznacza, że liczba
$m^5= m \cdot m^4$ należy do zbioru $T$ . Z drugiej strony, liczby $m, m^4$ są elementami zbioru $S$ ,
więc liczba $m^3$ nie może należeć do tego zbioru. Wobec tego $m, m^3, m^5 \in T$ .
Otrzymaliśmy zatem $m^2, m^3, m^5 \in T$ , czyli mamy sprzeczność.

Z drugiej strony, jeżeli podzielimy zbiór $\{m,m+1,\dots ,m^5 -1\}$ na następujące dwa podzbiory:

$ \begin{split} S &= \{m,m+1,\dots ,m^2 -2,m^2-1,m ,m^4 +1,\dots ,m^5 -2,m^5 -1\}, \\ T &= \{m^2 ,m^2 +1,\dots ,m^4 -2,m^4 -1\}, \end{split} $

to iloczyn dwóch elementów (niekoniecznie różnych) każdego z tych podzbiorów nie jest elementem tego
podzbioru. Rzeczywiście, do zbioru $T$ należą liczby nie mniejsze od $m^2$ , a więc iloczyn dowolnych dwóch
z nich jest równy co najmniej $m^4$ , zaś największym elementem tego zbioru jest liczba $m^4 -1$ . Z kolei do
zbioru $S$ należą liczby nie mniejsze od $m$ , więc iloczyn dowolnych dwóch jest równy co najmniej $m$ .
Iloczyn ten jest mniejszy od $m^4$ , jeżeli obie liczby są mniejsze od $m^2$ , albo jest równy przynajmniej
$m^5$ , jeżeli jedna z liczb wynosi co najmniej $m^4$ , i w obu przypadkach nie należy do zbioru $S$ .

Widzimy więc, że liczba $n = m^5 -1$ nie spełnia warunków zadania. Tym bardziej liczby
$n<m^5 - 1$ nie spełniają tych warunków, wystarczy bowiem z każdego ze zbiorów $S, T$ utworzonych dla wartości
$m^5 - 1$ usunąć liczby większe od $n$ . Wobec tego szukaną najmniejszą wartością jest $n = m^5$ .