KombinatorykaWyzwanieZadanie nr 3695
Największy podzbiór zbioru {1, …, 2026} bez dwóch liczb różniących się o 4 lub o 7
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\)?
Świetnie.
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
- 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.
- \(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\).
- 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\).
- 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.
Podobne zadania
- Permutacje liczb od 1 do 8 o naprzemiennie rosnących i malejących wyrazach
- Liczby od 1 do 11 na okręgu i iloczyny liczb stojących co drugie miejsce
- Największa rodzina parami przecinających się 4-elementowych podzbiorów zbioru {1, …, 12}
- Niemalejące ciągi długości 10 o wyrazach z {1, …, 12}, w których aᵢ ≠ i dla każdego i