Zadanie 4
2014
Etap I
★★★☆☆Kombinatoryka
Teoria liczb
Przyjęcie z 3 i 4 znajomymi
Powiązane zadania:
Zad. 2 (2011)
Treść zadania
Na przyjęcie przyszło osób. Początkowo każdy miał dokładnie 3 znajomych wśród pozostałych osób obecnych na przyjęciu. W trakcie przyjęcia niektóre osoby poznały się, w wyniku czego pod koniec przyjęcia każdy miał wśród pozostałych obecnych dokładnie 4 znajomych. Wyznacz wszystkie liczby , dla których opisana sytuacja jest możliwa. (Przyjmujemy, że jeśli osoba zna osobę , to osoba zna osobę .)
Umiejętności (5)
Wymagane umiejętności:
Grafy
Parzystość i nieparzystość
Zdobywane umiejętności:
Grafy
Podwójne zliczanie
Podzielność
Wskazówki (0/4)
Wskazówka 1
Zamiast analizować cały układ, zastanów się: ile dokładnie *nowych* znajomości zyskała każda osoba w trakcie przyjęcia?
Wskazówka 2
Rozważ graf złożony wyłącznie z tych nowych znajomości. Skoro każdy zyskał dokładnie 1 znajomego, to jak muszą wyglądać krawędzie w tym grafie?
Wskazówka 3
Struktura nowych znajomości (rozłączne pary) wymusza, aby liczba była parzysta. Czy jednak każde parzyste jest dopuszczalne? Pamiętaj o ograniczeniu na maksymalną liczbę znajomych.
Wskazówka 4
Aby każdy mógł mieć 4 znajomych, na przyjęciu musi być co najmniej 5 osób. Sprawdź, czy dla najmniejszej parzystej liczby spełniającej ten warunek (czyli ) potrafisz skonstruować odpowiedni przykład.