KombinatorykaWyzwanieZadanie nr 3695

Największy podzbiór zbioru {1, …, 2026} bez dwóch liczb różniących się o 4 lub o 7

Ekstremalne zbiory liczb Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

Jaka jest największa możliwa liczba elementów zbioru \(A\subseteq\{1,2,\dots,2026\}\), w którym żadne dwa elementy nie różnią się ani o \(4\), ani o \(7\)?

+18 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

Jak rozwiązać to zadanie?

Potrzebujesz pomocy? Pokaż wskazówkę

Rozważ bloki jedenastu kolejnych liczb: przejścia „o 4 w górę lub o 7 w dół” łączą je w jeden cykl. Do konstrukcji wybierz odpowiednie reszty z dzielenia przez \(11\).

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. W bloku \(\{m+1,\dots,m+11\}\) ustawmy liczby w kolejności \(m+1,m+5,m+9,m+2,m+6,m+10,m+3,m+7,m+11,m+4,m+8\) i z powrotem do \(m+1\): sąsiednie (także ostatnia z pierwszą) różnią się o \(4\) lub \(7\). To cykl długości \(11\), więc \(A\) zawiera z bloku co najwyżej \(5\) liczb.
  2. \(2026=184\cdot11+2\). Bloki \(\{11j+1,\dots,11j+11\}\), \(j=0,\dots,183\), dają co najwyżej \(5\cdot184=920\) elementów, a liczby \(2025,2026\) — co najwyżej \(2\). Zatem \(|A|\le922\).
  3. Konstrukcja: \(A\) — liczby dające z dzielenia przez \(11\) reszty \(1,2,4,7,10\). Różnice tych reszt modulo \(11\) to \(\pm1,\pm2,\pm3,\pm5,\pm6,\pm8,\pm9\) (sprawdzenie wszystkich dziesięciu par); żadna nie jest równa \(4\) ani \(7\), więc w \(A\) nie ma liczb różniących się o \(4\) ani o \(7\).
  4. Reszty \(1\) i \(2\) występują w \(\{1,\dots,2026\}\) po \(185\) razy, a pozostałe po \(184\): \(|A|=2\cdot185+3\cdot184=922\). Odpowiedź: \(922\).

Odpowiedź: \(922\)

Czego warto się nauczyć?

Kombinatoryka to sztuka liczenia bez wypisywania wszystkiego. Najważniejsze jest rozbicie problemu na etapy.

Więcej zadań z kombinatoryki →

Podobne zadania