Zadanie 2
2024
Etap III
★★★★☆Kombinatoryka
Teoria liczb
Impreza chłopców i dziewcząt
Treść zadania
W pewnej imprezie biorą udział chłopcy i dziewczęta. Każda z osób uczestniczących w tej imprezie zna wśród pozostałych osób dokładnie chłopców i dokładnie dziewcząt. Udowodnij, że liczba wszystkich osób uczestniczących w tej imprezie jest podzielna przez .
*Uwaga.* Zakładamy, że jeśli osoba zna osobę , to osoba zna osobę .
*Uwaga.* Zakładamy, że jeśli osoba zna osobę , to osoba zna osobę .
Umiejętności (5)
Wymagane umiejętności:
Podwójne zliczanie
Podzielność
Grafy
Zdobywane umiejętności:
Podwójne zliczanie
Podzielność
Wskazówki (0/4)
Wskazówka 1
Oznacz liczbę chłopców przez , a dziewcząt przez . Policz na dwa sposoby, ile jest łącznie znajomości między chłopcami a dziewczętami. Jaką zależność między i to daje?
Wskazówka 2
Z uzyskanej zależności wynika, że i są wielokrotnościami pewnych liczb. Zapisz sumę za pomocą jednego współczynnika. Czego jeszcze brakuje, aby udowodnić tezę?
Wskazówka 3
Rozważ teraz znajomości między osobami tej samej płci. Ile jest łącznie 'jednostronnych' zgłoszeń znajomości wśród samych chłopców? Jaka jest faktyczna liczba par znajomych chłopców?
Wskazówka 4
Liczba par znajomych chłopców musi być liczbą całkowitą. Jaki warunek nakłada to na liczbę chłopców ? Połącz ten wniosek z zależnością między i z pierwszej wskazówki.