Zadanie 5
2009
Etap III
★★★★★Kombinatoryka
Logika
Wielościan wypukły
Treść zadania
Czy istnieje wielościan wypukły mający dokładnie 100 ścian, z których przynajmniej jedna jest 99-kątem i taki, że w każdym jego wierzchołku zbiegają się dokładnie trzy krawędzie? Odpowiedź uzasadnij.
Umiejętności (5)
Wymagane umiejętności:
Wielościany
Podwójne zliczanie
Dowód nie wprost
Zdobywane umiejętności:
Wielościany
Podwójne zliczanie
Wskazówki (0/4)
Wskazówka 1
Zacznij od podstawowych własności wielościanów. Wzór Eulera łączy liczbę ścian (), wierzchołków () i krawędzi (). Jak powiązać i , wiedząc, że w każdym wierzchołku zbiegają się 3 krawędzie?
Wskazówka 2
Użyj wzoru Eulera i znalezionej zależności, aby obliczyć, ile wierzchołków i krawędzi musiałby mieć taki wielościan, gdyby istniał.
Wskazówka 3
Rozważmy graf utworzony z wierzchołków i krawędzi wielościanu. Co się stanie, jeśli usuniemy z niego 99 krawędzi tworzących ścianę 99-kątną? Policz, ile wierzchołków i krawędzi pozostanie.
Wskazówka 4
Jaki rodzaj grafu ma wierzchołków i krawędzi, jeśli jest spójny? Zauważ, że brzegi pozostałych 99 ścian muszą tworzyć w tym grafie cykle. Czy te dwa fakty da się pogodzić?