LIX OM - I -Zadanie 12

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:

\[<br /> \begin{split}<br /> S &= \{m,m+1,\dots ,m^2 -2,m^2-1,m ,m^4 +1,\dots ,m^5 -2,m^5 -1\}, \\<br /> T &= \{m^2 ,m^2 +1,\dots ,m^4 -2,m^4 -1\},<br /> \end{split}<br /> \]

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 $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź