Opis
Problemy działu matematyki, któremu poświęcone będą warsztaty dotyczą głównie badania kombinatorycznej struktury pewnych obiektów. Ich geometryczna natura wydaje się mieć tutaj drugorzędne znaczenie. Z drugiej strony, to właśnie ona sprawia, iż dane pytania są same w sobie bardzo interesujące i do złudzenia przypominają te, które znamy z olimpiad matematycznych. Nierzadko jednak ich rozstrzygnięcie okazuje się znacznie trudniejsze niż rozwiązanie zadania konkursowego…
Program
Orientacyjna lista tematów, które chciałbym poruszyć:
- Twierdzenia typu Helly'ego i ich zastosowania.
- Geometryczne własności zbioru $\mathbb{Z}^{2}$.
- O pewnych problemach pokryciowych.
- Wybrane zagadnienia dotyczące wielościanów wypukłych.
Forma: 2x wykład + 2x ćwiczenia (w+c+w+c)
Na ćwiczeniach, oprócz dowodzenia lematów z wykładów, rozwiązywalibyśmy zbliżone klimatycznie zadania olimpijskie.
Wymagania
Podstawy geometrii i kombinatoryki na poziomie liceum (znajomość rachunku wektorowego, najprostszych własności wielokątów/zbiorów wypukłych).
Zadania
1. Przyjmując definicję szkolną dowieść, że podzbiór płaszczyzny $S$ jest wypukły $\iff \forall{a,b \in S} \ \forall{ t \in [0,1]}$ $ta+(1-t)b \in S$ .
2. Dowieść, że figurę o polu $< 1$ można umieścić na płaszczyźnie tak, by nie przykrywała ona żadnego punktu kratowego.
3. Udowodnić, że koła o promieniu $R$ nie da się pokryć pasami o łącznej szerokości mniejszej niż $2R$.
4. Kwadrat o polu 1 jest sumą rozłącznych zbiorów $A$ i $B$. Pokazać, że istnieją 2 punkty, należące do jednego ze zbiorów tego podziału, odległe o nie mniej niż $\frac{\sqrt 5}{2}$.
5. Wykazać, że otoczka wypukła zbioru $X$ (najmniejszy zbiór wypukły zawierający $X$) jest równa
$conv(X) = \{ \sum^{k}_{i=1} \lambda_{i} x_{i} | \lambda_{i} \geq 0, k\in \mathbb{N}, x_{i} \in X, \sum^{k}_{i=1} \lambda_{i} = 1 \}$
6. Danych jest 5 punktów w położeniu ogólnym (na płaszczyźnie). Dowieść, że pewne 4 z nich wyznaczają czworokąt wypukły.
7. Danych jest n punktów na płaszczyźnie. Udowodnić, że są one wierzchołkami wielokąta wypukłego $\iff$ każde 4 z nich ma daną własność.
8. Mamy n punktów na płaszczyźnie (w położeniu ogólnym). Pokazać, że można je oznaczyć przez $P_{1}P_{2}..P_{n}$, by łamana $P_{1}P_{2}..P_{n}$ nie miała samoprzecięć.
9. Udowodnić własności sumy Minkowskiego:
- dla punktu $p$ zbiór $X+p$ jest obrazem $X$ przy translacji o $\overrightarrow{Op}$,
- $conv(X_{1}+...+X_{n})=conv(X_{1})+...+conv(X_{n})$.
10. (Kolejna własność dodawania Minkowskiego) Wykazać, że zbiór $S$ jest wypukły $\iff \forall \lambda_{1}, \lambda_{2} \geq 0 \ \lambda_{1}S+\lambda_{2} S = (\lambda_{1}+\lambda_{2})S$.
11. Znajdź wszystkie skończone zbiory punktów (w poł. ogólnym) płaszczyzny $S$ o następującej własności: dla każdych $A,B,C \in S$ istnieje w $S$ dopełnienie do równoległoboku.
Uwagi
*W niektórych z poniższych zadań wykonujemy rachunki na punktach; czynimy to jak z odpowiadającymi im wektorami, tj. dla $\alpha, \beta \in \mathbb{R}$ i punktów $a, b$ mamy $\overrightarrow{O(\alpha a + \beta b)} = \alpha\overrightarrow{Oa} + \beta \overrightarrow{Ob}$.
*Suma Minkowskiego zbiorów $A, B$ to zbiór $A+B = \{ a+b | a \in A, b \in B\}$.
*Położenie ogólne (dla $R^{2}$) ~ żadne 3 punkty nie leżą na jednej prostej, żadne 3 proste nie są współpękowe, etc.
*30-06-2012: poprawiono treści zadań 3 i 4.
Kontakt
moc.liamg|hsuoya.imar#moc.liamg|hsuoya.imar