Parcelacja meczu 2

1. Odległości _{}a mi_{}edzy dwoma wierzchołkami w grafie nieskierowanym nazywamy liczb_{}e równ _{}a 0, jeśli nie istnieje ścieżka mi_{}edzy tymi wierzchołkami lub też długość najkrótszej takiej ścieżki, jeśli istnieje. Średnic _{}a grafu nazywamy maksimum z odległości pomi_{}edzy wszystkimi parami wierzchołków. Dla grafu nieskierowanego G dopełnieniem grafu nazywamy graf maj _{}acy ten sam zbiór wierzchołków, ale w dopełnieniu każda para wierzchołków jest poł _{}aczona kraw_{}edzi _{}a wtedy i tylko wtedy, gdy w G nie była. Pokaz _{}ać, że dla każdego grafu nieskierowanego G on lub jego dopełnienie maj _{}a średnic_{}e nie wi_{}eksz _{}a niż 3.

2. Rozstrzygn _{}ać, czy istnieje takie n, że szachownic_{}e 3 × n można obejść skoczkiem szachowym odwiedzaj _{}ac każde pole dokładnie raz i wracaj _{}ac na koniec na pocz _{}atkowe pole.

3. Niech m, n b_{}ed _{}a takimi liczbami całkowitymi dodatnimi, że n m. Pokazać, że:

2^{n}n! \frac{(m + n)!}{(m − n)!} (m^{2} + m)^{n}

4. W trójk _{}acie ostrok _{}atnym ABC poprowadzono wysokość AD. Punkty E i F s _{}a różne od D i z D współliniowe oraz spełniaj _{}a warunki AE⊥BE oraz AF ⊥CF. Pokazać, że jeśli M i N to odpowiednio środki odcinków BC i EF, to AN⊥MN.

5. Wewn _{}atrz czworok _{}ata ABCD wpisanego w okr _{}ag istnieje taki punkt P, że

∠BP C = ∠BAP + ∠P DC

Punkty E, F, G s _{}a odpowiednio rzutami punktu P na proste AB, AD, CD. Pokazać, że trójk _{}aty F EG i P BC s _{}a podobne.

6. Pokazać, że jeśli w spójnym grafie dwudzielnym o liczbie wierzchołków co najmniej 3 wszystkie stopnie wierzchołków s _{}a równe, to usuni_{}ecie żadnej kraw_{}edzi z grafu go nie rozspójni.

7. Niech n b_{}edzie dowoln _{}a dodatni _{}a liczb _{}a całkowit _{}a parzyst _{}a. Udowodnić, że istnieje permutacja (x_{1}, x_{2}, …, x_{n}) zbioru {1, 2, …, n} spełniaj _{}aca dla każdego i ∈ {1, 2, …, n} warunek, że x_{i+1} ∈ {2x_{i}, 2x_{i} − 1, 2x_{i} − n, 2x_{i} − n − 1}, przy czym x_{n+1} = x_{1}.