Zadanie 4
2012
Etap I
★★☆☆☆Kombinatoryka
Bal z 102 królewiczami i 103 królewnami
Powiązane zadania:
Zad. 2 (2011)
Treść zadania
W balu wzięło udział 102 królewiczów i 103 królewny. Po balu okazało się, że każdy królewicz zatańczył z taką samą liczbą królewien. Udowodnij, że pewne dwie królewny zatańczyły z taką samą liczbą królewiczów.
Umiejętności (4)
Wymagane umiejętności:
Zasada szufladkowa
Grafy
Zdobywane umiejętności:
Zasada szufladkowa
Grafy
Wskazówki (0/4)
Wskazówka 1
Zastanów się, ile różnych wartości może przyjąć liczba królewiczów, z którymi mogła zatańczyć pojedyncza królewna. Jaki jest zakres tych wartości?
Wskazówka 2
Policz łączną liczbę wszystkich tańców (par królewicz-królewna) na dwa sposoby: raz sumując tańce z perspektywy wszystkich królewiczów, a raz z perspektywy wszystkich królewien.
Wskazówka 3
Załóż dla dowodu nie wprost, że każda królewna zatańczyła z inną liczbą królewiczów. Jaki zbiór liczb tworzyłyby wtedy liczby partnerów wszystkich 103 królewien?
Wskazówka 4
Oznacz przez stałą liczbę królewien, z którą zatańczył każdy królewicz. Zapisz równanie wynikające z podwójnego zliczenia i sprawdź, czy może być liczbą całkowitą.