Autor: Nauczyciel, Warszawa
Czytelnik musi zostać ostrzeżony, że w niniejszym artykule błyskotliwe chwyty prowadzić będą do gorszych wyników. Znacznie lepiej sprawdzą się brutalne, brudne metody. Kto liczy na zwycięstwo sprytu i dobrego stylu, niech lepiej zmieni lekturę.
Zadanie. Danych jest 7 liczb: 3, 5, 7, 9, 11, 13, 15. Zostały one w nieznany sposób podzielone na 3 grupy. Dla wybranej przez siebie liczby naturalnej \(k\) udowodnij, że iloczyn liczb w pewnej grupie musi wynieść co najmniej \(k.\) Im większe \(k,\) tym lepiej.
Sposób 1, \(k=105\). Wykorzystując zasadę szufladkową, można przekonać się, że w którejś z trzech grup muszą znaleźć się co najmniej 3 liczby. Istotnie, gdyby w każdej z trzech grup było nie więcej niż po dwie liczby, to łącznie byłoby ich nie więcej niż \(3\cdot 2=6 < 7.\) Iloczyn liczb w takiej grupie wynosi zaś co najmniej \(3\cdot 5\cdot 7=105.\)
O zasadzie szufladkowej pisaliśmy np. w \(\Delta^8_{04}\) oraz \(\Delta^9_{18}\).
Dziękuję Szymonowi Gramatnikowskiemu za zainspirowanie przedstawionego obok rozumowania.
Uwaga. Niekiedy oszacowanie tego rodzaju można poprawić, ignorując najmniejsze liczby, żeby skupić uwagę na większych. W tym przypadku, odrzucając liczby 3, 5, 7, pozostajemy z czterema: 9, 11, 13, 15. Są to 4 liczby w trzech grupach, więc któraś z grup musi zawierać przynajmniej dwie z nich. Jej iloczyn wynosi wówczas co najmniej \(9\cdot 11=99.\) Zgodnie z zapowiedzią spryt wcale nam się nie opłacił.
Sposób 2, \(k=127\). Aby poprawić poprzedni wynik, spróbujemy wykorzystać sztuczkę podobną do zasady szufladkowej, ale bezpośrednio do iloczynu danych liczb. Otóż gdyby iloczyn liczb w każdej z grup wynosił mniej niż \(127,\) to iloczyn wszystkich liczb we wszystkich grupach byłby nie większy od \(126 \cdot 126 \cdot 126 = 2 \, 000 \, 376.\) Jest to niemożliwe, bo iloczyn danych liczb jest nam znany i wynosi \(3\cdot 5\cdot 7 \cdot \ldots \cdot 15 = 2 \, 027 \, 025.\) Otrzymana sprzeczność dowodzi tezy.
Uwaga. Ponieważ \(127\cdot 127\cdot 127 = 2 \, 048 \, 383,\) więc technika ta nie zadziała dla żadnego większego \(k.\) Można natomiast nieco poprawić otrzymany wynik, zauważając, że iloczyn liczb w każdej grupie musi być dzielnikiem liczby \(2 \, 027 \, 025.\) Wyklucza to wszystkie liczby od 127 do 134 włącznie i pozwala uzyskać \(k=135.\)
Sposób 3, \(k=143\). Przypuśćmy, że iloczyn w każdej z grup jest mniejszy od 143. Analizując wszelkie możliwe sytuacje, doprowadzimy do sprzeczności. Grupę, w której skład wchodzi liczba 15, nazwiemy grupą czerwoną. W grupie tej może znajdować się jeszcze co najwyżej jedna liczba, bo w przeciwnym razie jej iloczyn wyniósłby co najmniej \(15\cdot 3\cdot 5=225.\) Liczbą tą może być co najwyżej 9, bo już \(15\cdot 11=165.\) Możemy bez straty ogólności założyć, że liczba 9 jest w czerwonej grupie (wyjaśnienie znajduje się na marginesie). Poza czerwoną grupą znajdują się liczby 3, 5, 7, 11, 13. Grupę, w której występuje 13, nazwiemy niebieską. Oprócz liczby 13 może być w niej jeszcze co najwyżej jedna liczba, bo już \(13\cdot 3\cdot 5=195.\) Liczba ta może być równa co najwyżej 7, bo \(13\cdot 11=143.\) Podobnie jak ostatnio, możemy założyć, że liczba 7 jest w grupie niebieskiej. Oznacza to, że w pozostałej grupie, którą nazwiemy żółtą, znajdują się liczby 3, 5, 11, których iloczyn wynosi 165! Otrzymaliśmy sprzeczność, która dowodzi tezy.
W ogólnym przypadku, jeśli liczba 9 nie jest w czerwonej grupie, to zamieńmy ją miejscami z liczbą mniejszą niż 15 z czerwonej grupy (jeżeli taka liczba nie istnieje, to po prostu dołóżmy 9 do tej grupy). W efekcie otrzymamy nowy podział na grupy, w którym liczba 9 już jest w czerwonej grupie, a ponadto jeśli iloczyn 142 nie był przekroczony wcześniej, to nadal nie będzie.
Uwaga. Osiągniętego tu oszacowania nie można już poprawić. Istotnie, jeśli w pierwszej grupie umieścimy liczby 3, 5, 7, w drugiej – 9 i 15, a w trzeciej 11 i 13, to otrzymujemy iloczyny 105, 135, 143, z których żaden nie jest większy od 143.
Powyższe przykłady obrazują, że im głębiej wejdzie się w strukturę problemu, im więcej jego szczególnych cech się wykorzysta, tym silniejsze wnioski można wyciągnąć. Tym niemniej, można docenić Sposoby 1 i 2, bo one również dają niezłe, być może zadowalające oszacowania, i to przy znacznie mniejszym nakładzie pracy. Tymczasem Sposób 3 wymagał bardzo skrupulatnej analizy, która byłaby znacznie trudniejsza do przeprowadzenia, gdyby danych liczb było nie 7, ale choćby 10.
Czytelnikowi pozostawiamy następujące wyzwanie.
Problem. Danych jest 9 liczb: 1, 3, 5, 7, 9, 11, 13, 15, 17. Zostały one w nieznany sposób dobrane w 4 grupy. Dla wybranej przez siebie liczby naturalnej \(k\) udowodnij, że iloczyn liczb w pewnej grupie musi wynieść co najmniej \(k.\) Im większe \(k,\) tym lepiej.