Własność kwadratów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11266
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Własność kwadratów

Post autor: mol_ksiazkowy »

Na płaszczyźnie jest skończona liczba kwadratów o równoległych bokach, takich że wśród dowolnych \(\displaystyle{ n}\) z nich istnieją cztery, które mają punkt wspólny. Udowodnić, że te wszystkie kwadraty można rozdzielić na \(\displaystyle{ n-3}\) części, takie, że kwadraty w każdej z nich mają punkt wspólny
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Własność kwadratów

Post autor: arek1357 »

Opowiadanko:

Zastanawiałem się nad tym i napiszę spostrzeżenia swoje, pomyślałem, że można te kwadraty pozamieniać na punkty grafu a jeżeli dwa kwadraty (punkty) mają jakieś punkty wspólne to łączymy je krawędzią. Tylko mówię od razu nie wiem jaki wpływ na to ma to, że krawędzie kwadratów są równoległe...

Można założyć, że tych punktów (kwadratów) jest \(\displaystyle{ m \ge n}\). Pod taką postacią można podejść do tego zadania...

Mamy w założeniu, że jeżeli weźmiemy dowolne n punktów to w każdej takiej entce będzie klika stopnia \(\displaystyle{ 4}\).
Moim celem jest pokazanie, że można tak łączyć krawędzie tego grafu, że ilość spójnych składowych będzie właśnie: \(\displaystyle{ n-3}\), bez względu na wielkość \(\displaystyle{ m}\), oczywiście można inaczej dzielić ten graf będzie inna ilość spójnych składowych ale zawsze będzie mniejsza lub równa \(\displaystyle{ n-3}\) - co jak łatwo zauważyć nie jest sprzeczne z treścią zadania...Ale trzymać się będę swojej koncepcji.
Ja chcę pokazać, że przy czymś takim uzyskać możemy (choć nie musimy) jedną klikę stopnia \(\displaystyle{ m-n+4}\) a pozostałe kliki(jednopunktowe w ilości: \(\displaystyle{ n-4}\)

Można tak założyć ponieważ zakładając, że wszystkich punktów mamy \(\displaystyle{ m}\), możemy na początek sobie wybrać podzbiór w tym zbiorze \(\displaystyle{ m}\) elementowym \(\displaystyle{ n+1}\) elementowy, w każdym podzbiorze zbioru \(\displaystyle{ n+1}\) elementowego \(\displaystyle{ n}\) elementowego mamy klikę czteroelementową wynika stąd, że w zbiorze \(\displaystyle{ n+1}\) elementowym przy pewnym łączeniu otrzymamy klikę pięcioelementową, bo jeżeli by jej nie było to istniałyby cztery punkty , które po dołożeniu \(\displaystyle{ n-4}\) punktów jeszcze nie połączonych nie byłoby kliki czteroelementowej w zbiorze \(\displaystyle{ n}\) elementowym. Więc jeżeli okazuje się, że w każdym zbiorze \(\displaystyle{ n+1}\) elementowym możemy się spodziewać kliki \(\displaystyle{ 5}\) elementowej to idąc za ciosem w każdym zbiorze \(\displaystyle{ n+2}\) elementowym możemy się spodziewać kliki sześcioelementowej, itd..., zawsze nie łączymy pozostałych punktów...I tak dojdziemy do kliki \(\displaystyle{ m-n+4}\) punktowej,
oprócz tego zostaje nam \(\displaystyle{ n-4}\) punkty wolne czyli trywialne kliki...
Oczywiście konstrukcje można inaczej wykonać ale wtedy ilość klik będzie mniejsza, co nie przeczy tezie zadania bo zawsze kliki te można podzielić na zbiory spełniające warunki zadania...
ODPOWIEDZ