Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
W kwadratowa tablice składającą się z \(\displaystyle{ 81}\) jednakowych kwadratowych pól wpisano wszystkie liczby naturalne od \(\displaystyle{ 1}\) do \(\displaystyle{ 81}\). Udowodnij, ze dla dowolnego ułożenia liczb istnieją dwie sąsiednie różniące się co najmniej o \(\displaystyle{ 6}\). Przez sąsiednie rozumiemy liczby wpisane w pola o wspólnej krawędzi.
Ostatnio zmieniony 31 mar 2013, o 04:03 przez Ponewor, łącznie zmieniany 2 razy.
Powód:Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
Zadanie pojawiło się w \(\displaystyle{ 101}\) nierozwiązanych.
Rozwiązanie:
Teza zadania: Dla dowolnego ułożenia wszystkich liczb naturalnych od \(\displaystyle{ 1}\) do \(\displaystyle{ 81}\) w kwadratowej tablicy składającej się \(\displaystyle{ 81}\) jednakowych kwadratowych pól, istnieją dwie sąsiednie różniące się co najmniej o \(\displaystyle{ 6}\).
Dowiedziemy mocniejszej tezy: Teza wzmocniona: Dla dowolnego ułożenia wszystkich liczb naturalnych od \(\displaystyle{ 1}\) do \(\displaystyle{ 81}\) w kwadratowej tablicy składającej się \(\displaystyle{ 81}\) jednakowych kwadratowych pól, istnieją dwie sąsiednie różniące się co najmniej o \(\displaystyle{ 9}\).
A nawet ją uogólnimy: Teza uogólniona: Dla każdej liczby naturalnej \(\displaystyle{ n \ge 2}\), dla dowolnego ułożenia wszystkich liczb naturalnych od \(\displaystyle{ 1}\) do \(\displaystyle{ n^{2}}\) w kwadratowej tablicy składającej się \(\displaystyle{ n^{2}}\) jednakowych kwadratowych pól, istnieją dwie sąsiednie różniące się co najmniej o \(\displaystyle{ n}\). Dowód:
Załóżmy nie wprost, że liczby na dowolnych dwóch polach o wspólnej krawędzi różnią się o mniej niż \(\displaystyle{ n}\). Popatrzmy na zbiory \(\displaystyle{ A_{i}=\left\{ 1, \ 2, \ \ldots, \ i \right\}}\) i \(\displaystyle{ B_{i}=\left\{ i+n, \ i+n+1, \ \ldots, \ \ n^{2}\right\}}\), przy czym z racji przyzwoitości niech \(\displaystyle{ i=1, \ 2, \ \ldots , \ n^{2}-n}\). Oczywiście nie istnieją dwa pola o wspólnej krawędzi z liczbami należącymi do obu tych zbiorów. Załóżmy, że w każdej kolumnie istnieją pola z liczbami i ze zbioru \(\displaystyle{ A_{i}}\) i z \(\displaystyle{ B_{i}}\). Wobec tego w każdej kolumnie musi być choć jedno pól nienależących do tamtych zbiorów (bo jakoś trzeba je rozdzielić), których jest: \(\displaystyle{ \left| \left(A_{i} \cup B_{i}\right)'\right|=n^{2}-\left(i+\left(n^{2}-\left(i+n\right)+1\right)\right)=n-1 <n}\) czyli sprzeczność, bo kolumn jest \(\displaystyle{ n}\). Zatem istnieje kolumna w której są pola z liczbami z tylko jednego zbioru. Analogicznie istnieje wiersz z polami z liczbami z tylko jednego zbioru. Z uwagi na fakt, że każdy wiersz i każda kolumna mają wspólne pole i \(\displaystyle{ A_{i} \cap B_{i} = \emptyset}\) to istnieją wiersz i kolumna z polami z liczbami z tylko jednego z tych zbiorów, który będziemy zwać wyróżnionym. Istnieją i takie konfiguracje w których jest to zbiór \(\displaystyle{ A_{i}}\) (wystarczy położyć \(\displaystyle{ i=n^{2}-n}\)), oraz takie w których jest to zbiór \(\displaystyle{ C_{i}}\) (wystarczy położyć \(\displaystyle{ i=1}\)). Teraz już łatwo, bo skoro istnieją takie naturalne \(\displaystyle{ i}\) dla których wyróżniony jest zbiór \(\displaystyle{ A_{i}}\), to jak to bywa wśród liczb naturalnych istnieje najmniejsze \(\displaystyle{ i}\), dla którego \(\displaystyle{ A_{i}}\) jest wyróżniony. Nie jest to oczywiście \(\displaystyle{ i=1}\). Skoro tak, to \(\displaystyle{ A_{i-1}}\) nie jest zbiorem wyróżnionym, ale dla każdego \(\displaystyle{ i}\) musi istnieć zbiór wyróżniony, więc \(\displaystyle{ B_{i-1}}\) jest zbiorem wyróżnionym. Kolumna w której są pola z liczbami jedynie ze zbioru \(\displaystyle{ A_{i}}\) tnie wiersz z polami w których są liczby jedynie ze zbioru \(\displaystyle{ B_{i-1}}\). Istnieje więc pole z liczbą należącą do \(\displaystyle{ A_{i}}\) i jednocześnie \(\displaystyle{ B_{i-1}}\), ale \(\displaystyle{ A_{i} \cap B_{i-1} = \emptyset}\), bo najmniejsza liczba ze zbioru \(\displaystyle{ B_{i-1}}\) równa \(\displaystyle{ n+i-1}\) jest dla \(\displaystyle{ n \ge 2}\) większa od największej liczby ze zbioru \(\displaystyle{ A_{i}}\) równej \(\displaystyle{ i}\). Otrzymana sprzeczność dowodzi tezy.
