[MIX][Kombinatoryka] Grafy

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

[MIX][Kombinatoryka] Grafy

Post autor: Mruczek »

1. Czy siedmiokąt można pociąć na sześciokąty wypukłe?
2. W kwadracie zaznaczmy \(\displaystyle{ n}\) punktów i łączymy je odcinkami, które nie przecinają się między sobą w punktach wewnętrznych oraz z wierzchołkami kwadratu w taki sposób, że kwadrat został rozcięty na trójkąty. Żadne trzy z tych punktów i wierzchołków kwadratu nie leżą na jednej prostej. Uzasadnij ile otrzymano trójkątów.
3. \(\displaystyle{ 15}\) drużyn rozgrywa turniej każdy z każdym. Pokazać, że w pewnym meczu spotkają się drużyny, które zagrały dotychczas w sumie nieparzystą ilość spotkań.
4. Pokazać, że w \(\displaystyle{ 17}\) osobowym towarzystwie, w którym każda osoba zna cztery inne, znajdą się dwie osoby, które się nie znają i nie mają wspólnych znajomych.
5. W grupie jest \(\displaystyle{ 30}\) osób. Każdej osobie podoba się dokładnie \(\displaystyle{ n}\) osób z grupy. Przy jakiej minimalnej wartości \(\displaystyle{ n}\) prawdziwe jest stwierdzenie: "w grupie są dwie osoby, które się podobają sobie nawzajem"?
6. W pewnym państwie jest \(\displaystyle{ n}\) miast. Pomiędzy każdymi dwoma jest droga jednokierunkowa. Pokazać, że istnieje miasto, z którego można dojechać do każdego innego miasta z nie więcej niż jedną przesiadką.
7. Czy można \(\displaystyle{ 10}\) miast połączyć ze sobą nieprzecinającymi się drogami w taki sposób, aby z każdego miasta wychodziło po \(\displaystyle{ 5}\) dróg prowadzących do \(\displaystyle{ 5}\) innych miast?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: [MIX][Kombinatoryka] Grafy

Post autor: kerajs »

A co to są grafy?
1:    

2:    
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: [MIX][Kombinatoryka] Grafy

Post autor: kerajs »

3:    
5:    
7:    
Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

Re: [MIX][Kombinatoryka] Grafy

Post autor: Swistak »

kerajs pisze:
2:    
To jest blef. Nie każdy taki układ możesz tak budować poprzez dorzucanie po jednym punkcie. Narysuj se dowolny trójkąt wewnątrz kwadratu, a potem odpowiednio połącz jego wierzchołki z wierzchołkami kwadratu. Niemniej odpowiedź poprawna, bo ciężko aby była zła .
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: [MIX][Kombinatoryka] Grafy

Post autor: kerajs »

Jaki blef? Podział który wskazałem zawsze można wykonać i z niego łatwo można wyliczyć ilość uzyskanych trójkątów. Nigdzie nie napisałem że to jedyny sposób podziału.
Przyznaję, wskazana nieścisłość jest słabością rozwiązania, jednak wtedy cały post był napisany na szybko i wyłącznie dla żartu, aby zdążyć przed zalewem rozwiązań (lub linków do rozwiązań) z użyciem grafów.
Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

Re: [MIX][Kombinatoryka] Grafy

Post autor: Swistak »

A skąd wiesz, że to jedyna możliwa odpowiedź? Może jakimiś innymi podziałami da się uzyskać jakąś inną wartość? Takie rozumowanie może być dobre na Kangurze, gdzie trzeba jedynie dojść do dobrej odpowiedzi i zaznaczyć dobry kwadracik, ale jako dowód matematyczny jest niewiele warte.
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

Re: [MIX][Kombinatoryka] Grafy

Post autor: Mruczek »

Alternatywne podejście do zadania 3:

Kod: Zaznacz cały

https://artofproblemsolving.com/community/c6h411670p2310159
ODPOWIEDZ