Krata i Wielokąt
- mol_ksiazkowy
- Użytkownik
- Posty: 11583
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3167 razy
- Pomógł: 749 razy
Krata i Wielokąt
Udowodnić, że wielokąt o polu większym od \(\displaystyle{ n}\) można przesunąć tak, by w jego wnętrzu było co najmniej \(\displaystyle{ n+1}\) punktów kratowych.
- JHN
- Użytkownik
- Posty: 675
- Rejestracja: 8 lip 2007, o 18:09
- Płeć: Mężczyzna
- Lokalizacja: Radom
- Podziękował: 7 razy
- Pomógł: 211 razy
Re: Krata i Wielokąt
Z wzoru Picka: \(p=w+{1\over2}b-1\). Jeśli \(p>n\) oraz zagwarantujemy \(b=0\), to \(w+0-1>n\) i teza jest prawdziwa.
Pozdrawiam
Pozdrawiam
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Wz%C3%B3r_Picka[icode]
-
- Użytkownik
- Posty: 22276
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3765 razy
Re: Krata i Wielokąt
To nie ma nic wspólnego z zadaniem. We wzorze Picka chodzi o wielokąty o wierzchołkach w punktach kratowych. A do wielokąta w zadaniu i do ich przesunięć to twierdzenie może nie być stosowalne
- arek1357
- Użytkownik
- Posty: 5750
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 132 razy
- Pomógł: 526 razy
Re: Krata i Wielokąt
To zadanie idzie łatwo z "polowej" wersji Dirichleta, a mianowicie:
Z: \(\displaystyle{ \sum_{}^{} |A_{i}|>n|X|}\)
Oraz: \(\displaystyle{ A_{i}}\) - pokrycia zbioru \(\displaystyle{ X}\)
T: Istnieje taki punkt \(\displaystyle{ x \in X}\), który należy przynajmniej do \(\displaystyle{ n+1}\) zbiorów \(\displaystyle{ A_{i}}\)
Teraz wystarczy podzielić wielokąt W na \(\displaystyle{ K_{j}}\) - kwadraty jednostkowe
I pokryć go zbiorami:
\(\displaystyle{ W= \sum_{}^{} W \cap K_{j}}\)
Potem zbiory :\(\displaystyle{ W \cap K_{j}}\) położyć na jednym kwadracie jednostkowym,
Oczywiście zgodnie z zadaniem:
\(\displaystyle{ \sum_{}^{} W \cap K_{j} > n \cdot 1}\)
Znacz, że istnieje taki punkt \(\displaystyle{ x}\), który należy do przynajmniej \(\displaystyle{ n+1 }\) zbiorów:
\(\displaystyle{ W \cap K_{j}}\)
Potem te zbiorki rozsuniemy tak, żeby powstała figura \(\displaystyle{ W}\), i z twgo będziemy mieć \(\displaystyle{ n+1}\) klonów punktu \(\displaystyle{ x}\)
Identycznie umieszczonych w kwadratach jednostkowych, wystarczy teraz tak pociągnąć figurę \(\displaystyle{ W}\), żeby punkt \(\displaystyle{ x}\)
wraz z klonami znalazł się w lewym dolnym rogu kwadratu, który jest kratowy, cnd...
Nie wiem czy trzeba zakładać, że \(\displaystyle{ W}\) to wielokąt...
Z: \(\displaystyle{ \sum_{}^{} |A_{i}|>n|X|}\)
Oraz: \(\displaystyle{ A_{i}}\) - pokrycia zbioru \(\displaystyle{ X}\)
T: Istnieje taki punkt \(\displaystyle{ x \in X}\), który należy przynajmniej do \(\displaystyle{ n+1}\) zbiorów \(\displaystyle{ A_{i}}\)
Teraz wystarczy podzielić wielokąt W na \(\displaystyle{ K_{j}}\) - kwadraty jednostkowe
I pokryć go zbiorami:
\(\displaystyle{ W= \sum_{}^{} W \cap K_{j}}\)
Potem zbiory :\(\displaystyle{ W \cap K_{j}}\) położyć na jednym kwadracie jednostkowym,
Oczywiście zgodnie z zadaniem:
\(\displaystyle{ \sum_{}^{} W \cap K_{j} > n \cdot 1}\)
Znacz, że istnieje taki punkt \(\displaystyle{ x}\), który należy do przynajmniej \(\displaystyle{ n+1 }\) zbiorów:
\(\displaystyle{ W \cap K_{j}}\)
Potem te zbiorki rozsuniemy tak, żeby powstała figura \(\displaystyle{ W}\), i z twgo będziemy mieć \(\displaystyle{ n+1}\) klonów punktu \(\displaystyle{ x}\)
Identycznie umieszczonych w kwadratach jednostkowych, wystarczy teraz tak pociągnąć figurę \(\displaystyle{ W}\), żeby punkt \(\displaystyle{ x}\)
wraz z klonami znalazł się w lewym dolnym rogu kwadratu, który jest kratowy, cnd...
Nie wiem czy trzeba zakładać, że \(\displaystyle{ W}\) to wielokąt...