Troch_{}e grafowo

wtorek, 3 marca 2009

1. Udowodnij, że można pokolorować wierzchołki grafu planarnego, używaj _{}ac trzech kolorów, tak by nie istniał trójk _{}at o wierzchołkach w tych samych kolorach.

2. Wielomian n-tego stopnia spełnia: P (1) = 1, P (2) = \frac{1}{2}, P (4) = \frac{1}{4}, …, P (2^{n}) = \frac{1}{2^{n}} . Znajdź P (0).

3. Każdy ze zbiorów A_{1}, A_{2}, ⋯, A_{n} ma k elementów (k 1) oraz każdy element x ∈ X należy do co najwyżej k ze zbiorów A_{i}. Udowodnij, że istnieje k systemów różnych reprezentantów, o tej własności, że dla każdego i wszystkie elementy reprezentuj _{}ace A_{i} s _{}a różne (i wyczerpuj _{}a cały zbiór A_{i}).

4. t_{i} to i − ty wyraz słowa Thue-Morse’a. Niech:

I = {i ∈ {1, 2, …, 2^{N} − 1} : t_{i} = 0} J = {j ∈ {1, 2, …, 2^{N} − 1} : t_{j} = 1} Udowodnij, że dla 0 k N − 1 zachodzi: ∑ _{i∈I} i^{k} = ∑ _{j∈J} j^{k}.

5. Jako, że wiosna już przyszła, ogrodnik Piotr, zamiast przyjść na kółko, postanowił zasadzić kwiatki w swoim ogrodzie. Ogród Piotra jest nieskończon _{}a płaszczyzn _{}a z naniesionym układem współrz_{}ednych. W N punktach kratowych (tzn. tych o obu współrz_{}ednych całkowitych) Piotr postanowił posadzić po jednym kwiatku - róży lub goździku. Ogrodnik b_{}edzie uważał, że jego ogród jest pi_{}ekny tylko wtedy, gdy na każdej prostej równoległej do którejkolwiek osi układu (tzn. poziomej lub pionowej) liczba róż i goździków b_{}edzie si_{}e różniła co najwyżej o 1. Udowodnij, że może tak zasadzić kwiaty w tych N punktach, by uczynić swój ogród pi_{}eknym.

6. Punkty K i L leż _{}a na bokach AB i AC trójk _{}ata ABC tak, że BK=CL. Niech P b_{}edzie punktem przeci_{}ecia CK i BL. Prosta równoległa do dwusiecznej k _{}ata wewn_{}etrznego BAC trójk _{}ata przecina AC w punkcie M. Pokazać, że CM=AB.