4. podzimní série Téma:
Množiny
Datum odeslání:
10. ledna 2011
1. úloha
(3 body)
Do jedné nejmenované čajovny chodí každý víkend několik pravidelných hostů. Každý z nich má nějaké oblíbené druhy čaje – zelený, černý nebo bílý. Někteří z hostů si dávají vždy ten samý druh čaje, jiní mají v oblibě dva druhy a někteří si rádi objednají kterýkoliv čaj. Alča si všimla, že právě 42 z pravidelných hostů jsou tací, kteří si buď bílý čaj nedávají nikdy, nebo ho střídají s jedním jiným druhem či oběma ostatními. Dále je celkem 28 těch, kteří zelený čaj pijí vždy nebo alespoň občas, a konečně 9 hostů si sice nikdy zelený čaj nedá, ale jinak mají rádi jak černý, tak bílý. Alču by teď zajímalo, kolik hostů nepije nic jiného než černý čaj. Pomůžete jí? 2. úloha
(3 body)
Jarda se naštval na množinu M = {1, 2, . . . , 12} a začal z ní vyhazovat čísla. Bylo to však těžší, než čekal – když z M vyhodil nějaké číslo různé od 1, mohl potom vyhodit pouze číslo s ním soudělné nebo jedničku. Pokud vyhodil jedničku, mohl jako další číslo vyhodit jakékoliv jiné. Kolik nejvíc čísel mohl Jarda z M vyhodit? 3. úloha
(3 body)
Při svých toulkách rovinou objevil Olin pozoruhodnou množinu bodů, která byla osově souměrná podle úplně všech přímek v rovině. Určete všechny neprázdné množiny, které mohl Olin najít. 4. úloha
(5 bodù)
Čísla 1, 2, . . . , 2011 rozházíme do tří různobarevných kyblíčků – bílého, modrého a červeného. Kolika způsoby můžeme čísla rozházet, pokud žádný z nich není prázdný a dvě po sobě jdoucí čísla nikdy nejsou v témže kyblíčku? 5. úloha
(5 bodù)
Je dán trojúhelník ABC a na jeho kružnici opsané bod X různý od vrcholů A, B, C. Označme D, E paty kolmic vedených z bodu X postupně na přímky AB, BC. Určete množinu středů kružnic opsaných trojúhelníkům XDE pro všechny přípustné body X. 6. úloha
(5 bodù)
Mějme n-prvkovou množinu kladných reálných čísel1 A = {a1 , a2 , . . . , an }. Dokažte, že pokud vezmeme všechny možné neprázdné podmnožiny A a sečteme jejich prvky, dostaneme alespoň 1 n(n + 1) různých čísel. 2 7. úloha
Kennyho množina přirozených čísel K má následující vlastnosti: (i) 1 ∈ K, (ii) pokud x ∈ K, tak také 4x ¨√ ∈˝K, x ∈ K, (iii) pokud x ∈ K, tak také 1Z
vlastností množin plyne, že tato čísla musí být nutně různá.
(5 bodù)
kde symbol ⌊k⌋ značí dolní celou část čísla k, tj. největší celé číslo, které je menší nebo rovno k. Dokažte, že K je množina všech přirozených čísel. 8. úloha
(5 bodù)
Je dána n-prvková množina M přirozených čísel a přirozené číslo m splňující 1 ≤ m ≤ n + 1. Dokažte, že existuje alespoň 2n−m+1 podmnožin M se součtem prvků2 dělitelným m.
2 Součet
prvků prázdné množiny je 0.
Řešení 4. podzimní série 1. úloha Do jedné nejmenované čajovny chodí každý víkend několik pravidelných hostů. Každý z nich má nějaké oblíbené druhy čaje – zelený, černý nebo bílý. Někteří z hostů si dávají vždy ten samý druh čaje, jiní mají v oblibě dva druhy a někteří si rádi objednají kterýkoliv čaj. Alča si všimla, že právě 42 z pravidelných hostů jsou tací, kteří si buď bílý čaj nedávají nikdy, nebo ho střídají s jedním jiným druhem či oběma ostatními. Dále je celkem 28 těch, kteří zelený čaj pijí vždy nebo alespoň občas, a konečně 9 hostů si sice nikdy zelený čaj nedá, ale jinak mají rádi jak černý, tak bílý. Alču by teď zajímalo, kolik hostů nepije nic jiného než černý čaj. Pomůžete jí? (Alča Skálová) Inspirováno řešením Lenky Staré: ˇ v obrázku Zadané informace můžeme vyjádřit pomocí Vennových diagramů. Písmena Z, B a C značí množiny lidí, kteří pijí po řadě zelený, bílý a černý čaj. 42
28
9 Z
Cˇ
Z
Cˇ
Z
B
B
Cˇ
Z
B
B
a) 42 lidí nepije samotný bílý čaj, jinak pijí libovolné kombinace čajů, b) 28 lidí pije v libovolné kombinaci zelený čaj, c) 9 lidí pije bílý i černý, ale ne zelený čaj. Hledaný počet lidí získáme odečtením velikostí množin na obrázcích b) a c) od velikosti množiny na obrázku a). Jelikož 42 − 28 − 9 = 5, tak hostů, kteří mají rádi jen černý čaj, je pět. 2. úloha Jarda se naštval na množinu M = {1, 2, . . . , 12} a začal z ní vyhazovat čísla. Bylo to však těžší, než čekal – když z M vyhodil nějaké číslo různé od 1, mohl potom vyhodit pouze číslo s ním soudělné nebo jedničku. Pokud vyhodil jedničku, mohl jako další číslo vyhodit jakékoliv jiné. Kolik nejvíc čísel mohl Jarda z M vyhodit? (Jarda „Jardáčÿ Hančl) Pokud bude Jarda vyhazovat čísla v pořadí 5, 10, 2, 4, 6, 8, 12, 9, 3, 1, 7, může jich vyhodit celkem jedenáct. Dokažme, že všech dvanáct čísel Jarda vyhodit nemůže. Všimněme si, že čísla 7 a 11 jsou nesoudělná se všemi ostatními čísly z M . Těsně před nimi a těsně po nich může tedy Jarda vyhodit pouze číslo 1. To znamená, že pokud chce Jarda vyhodit sedmičku i jedenáctku, musí těsně po sobě vyházet čísla 7, 1, 11, anebo čísla 11, 1, 7. Tak či tak už nemůže předtím ani poté vyhodit žádné jiné číslo. Všech dvanáct čísel tedy z M vyhodit nelze a jedenáct je hledané maximum.
3. úloha Při svých toulkách rovinou objevil Olin pozoruhodnou množinu bodů, která byla osově souměrná podle úplně všech přímek v rovině. Určete všechny neprázdné množiny, které mohl Olin najít. (Alexander „Olinÿ Slávik)
Ukážeme, že pokud nějaká neprázdná množina M vyhovuje podmínkám ze zadání, pak už do ní nutně patří všechny body roviny. Množina M je neprázdná, existuje tedy nějaký bod X, který jí náleží. Zvolme nyní v rovině libovolný bod Y různý od X. Protože je M osově souměrná podle všech přímek v rovině, je souměrná i podle osy úsečky XY . V osové souměrnosti podle této osy se však bod X zobrazí na bod Y , tudíž i bod Y musí náležet M . Protože bod Y byl volen libovolně, patří do M každý bod různý od X (a samozřejmě do ní patří i X). Dostáváme tedy, že jediná množina, která může vyhovovat zadaným podmínkám, je celá rovina a ta podmínky zřejmě splňuje.
4. úloha Čísla 1, 2, . . . , 2011 rozházíme do tří různobarevných kyblíčků – bílého, modrého a červeného. Kolika způsoby můžeme čísla rozházet, pokud žádný z nich není prázdný a dvě po sobě jdoucí čísla nikdy nejsou v témže kyblíčku? (Lenka Slavíková)
Uvažujme najprv iba druhú podmienku. Čísla budeme rozdeľovať postupne od 1 po 2011. Pre jednotku máme na výber zo všetkých troch kýblikov. Pre každé ďalšie číslo je vždy v niektorom kýbliku číslo o jedna menšie, teda na výber nám ostanú len dva kýbliky. Všetkých 2011 čísel preto vieme rozdeliť 3 · 2 · · · 2 = 3 · 22010 spôsobmi. Teraz uplatníme prvú podmienku. Zistíme, koľko z predošlých rozdelení necháva jeden kýblik prázdny (viac ich vďaka druhej podmienke byť nemôže). Pre jednotku máme opäť na výber z troch kýblikov a pre dvojku z dvoch. Všetky ostatné čísla už sú jasne dané, pretože nesmú ísť k predcházajúcemu číslu ani naplniť doposiaľ prázdny kýblik. To nám dáva 3 · 2 · 12009 „zlýchÿ rozdelení. Rozdelení vyhovujúcich zadaniu je teda 3 · 22010 − 6 = 6(22009 − 1).
5. úloha Je dán trojúhelník ABC a na jeho kružnici opsané bod X různý od vrcholů A, B, C. Označme D, E paty kolmic vedených z bodu X postupně na přímky AB, BC. Určete množinu středů kružnic opsaných trojúhelníkům XDE pro všechny přípustné body X. (Michal „Kennyÿ Rolínek)
C
X
E
A
S
D
B
Ze zadání vyplývá, že úhel ∢BDX je pravý, a proto bod D podle Thaletovy věty leží na kružnici s průměrem BX. Obdobně na ní leží i bod E. To znamená, že pro libovolnou volbu bodu X je středem kružnice opsané trojúhelníku XDE střed úsečky BX. Označme ho S. Ekvivalentně tedy hledáme množinu středů všech možných úseček BX. Bod S příslušný danému X získáme pomocí stejnolehlosti se středem v bodě B a koeficientem 1 . Hledanou množinou je obraz kružnice opsané trojúhelníku ABC bez bodů A, B, C (tj. obraz 2 množiny všech možných X) v této stejnolehlosti. Obráceně ke každému bodu S této množiny lze najít bod X pomocí stejnolehlosti se středem v bodě B a koeficientem 2. 6. úloha Mějme n-prvkovou množinu kladných reálných čísel3 A = {a1 , a2 , . . . , an }. Dokažte, že pokud vezmeme všechny možné neprázdné podmnožiny A a sečteme jejich prvky, dostaneme alespoň 1 n(n + 1) různých čísel. (Pepa Tkadlec) 2 Budeme-li hovořit o součtu nějaké množiny, máme na mysli součet jejích prvků. V n krocích zkonstruujeme 21 n(n+1) neprázdných podmnožin A, o kterých následně ukážeme, že mají po dvou různé součty, čímž budeme hotovi. V prvním kroku konstrukce uvažme všechny jednoprvkové podmnožiny (těch je n). Ve druhém kroku uvažme všechny dvouprvkové podmnožiny, které obsahují největší číslo (těch je n − 1). Obecně v k-tém kroku uvažme ty k-prvkové podmnožiny množiny A, které obsahují k − 1 největších čísel a k tomu jedno další (těch je n − k + 1). V posledním, n-tém kroku uvažme v souladu s předchozím popisem celou množinu A. Tím jsme vybrali celkem n + (n − 1) + · · · + 1 = 21 n(n + 1) množin. Teď ukážeme, že tyto množiny mají po dvou různé součty. Prvně si uvědomíme, že libovolné dvě množiny vybrané v rámci jednoho kroku se liší v právě jednom prvku. Jelikož prvky množiny A jsou po dvou různá čísla, jsou i součty každých dvou množin (v rámci jednoho kroku) různé. Zbývá si povšimnout, že množina vybraná v (k + 1)-tém kroku obsahuje krom k největších čísel množiny A ještě jedno kladné číslo. Její součet je proto větší než součet libovolné k-prvkové množiny, tedy i větší než součet každé množiny vybrané v kroku k-tém nebo nižším. Tím jsme již zaručili různost součtů všech vybraných množin. Jsme hotovi. 3Z
vlastností množin plyne, že tato čísla musí být nutně různá.
7. úloha Kennyho množina přirozených čísel K má následující vlastnosti: (i) 1 ∈ K, (ii) pokud x ∈ K, tak také 4x ¨√ ∈˝K, (iii) pokud x ∈ K, tak také x ∈ K,
kde symbol ⌊k⌋ značí dolní celou část čísla k, tj. největší celé číslo, které je menší nebo rovno k. Dokažte, že K je množina všech přirozených čísel. (Michal „Kennyÿ Rolínek) V množině K jistě jiná než přirozená čísla nejsou. Pro spor dále předpokládejme, že existuje n ˙∈ N, které neleží v K. Díky (iii) ´ ¨√ ˝potom nemůže být v K ani žádné přirozené číslo c z intervalu n2 , (n + 1)2 , jinak by n = c ∈ K. Stejnou ˙ ´ úvahou pro čísla z tohoto intervalu zjistíme, že prvky K nejsou ani čísla z intervalu n4 , (n + 1)4 . ˙ 2k ´ k Triviální indukcí dostáváme, že K neprotíná žádný interval tvaru n , (n + 1)2 , k ∈ N. Na druhou stranu z (i) a (ii) plyne, že K obsahuje všechny přirozené mocniny čtyř. Pro spor tedy stačí najít mocninu čtyř v některém z intervalů výše uvedeného tvaru. Protože n+1 > 1, můžeme najít t ∈ N takové, že n „
n+1 n
« 2t
> 4. t
Označíme-li teď 4m největší mocninu čísla 4 menší než n2 , pak t
t
t
n2 ≤ 4m+1 = 4 · 4m < 4 · n2 < (n + 1)2 . Našli jsme (m + 1)-tou mocninu čtyř v t-tém intervalu, čímž je spor dokonán. 8. úloha Je dána n-prvková množina M přirozených čísel a přirozené číslo m splňující 1 ≤ m ≤ n + 1. Dokažte, že existuje alespoň 2n−m+1 podmnožin M se součtem prvků4 dělitelným m. (Michal „Kennyÿ Rolínek) Řešení podle Dominika Lachmana: Mějme nějaké m a převeďme si čísla z n-prvkové množiny M na zbytky po dělení číslem m. Definujme ai pro i od 0 do m − 1 jako počet podmnožin, pro něž platí, že součet jejich prvků dává po dělení m zbytek i. Chceme ukázat, že a0 ≥ 2n−m+1 . Dokážeme silnější tvrzení. Tvrdíme, že pokud amin značí hodnotu nejmenšího nenulového ai a P počet nulových ai , pak amin ≥ 2n−m+1+P . To nám spolu s pozorováním, že a0 je nenulové (a tedy alespoň tak velké jako amin ) a nerovností 2n−m+1+P ≥ 2n−m+1 dá požadovaný výsledek. Pro důkaz postupujme indukcí podle n. Pro n = 0 je a0 = 1 a všechna ostatní ai = 0. Je proto amin = a0 = 1 a P = m − 1 a skutečně platí 1 ≥ 20−m+1+(m−1) . Teď zvýšíme n o jedna. Označme M ′ množinu, která vznikne sjednocením množiny M a nějakého prvku x. Označme a′i (pro i od 0 do m − 1) počet podmnožin množiny M ′ , jejichž 4 Součet
prvků prázdné množiny je 0.
součet prvků dává po dělení číslem m zbytek i. Označme také „novéÿ hodnoty amin , P jako a′min , P ′ . Podmnožiny M ′ dávající zbytek i po dělení číslem m jsou dvou typů – ty, které neobsahují x, a ty, které x obsahují. Těch prvních je ai , těch druhých je ai−x , kde index uvažujeme cyklicky, tj. modulo m. Pro každé i = 0, . . . , m − 1 tedy dostáváme a′i = ai + ai−x . (Množinu čísel a′i pro i = 0, . . . , m − 1 v jisté představě získáme tak, že množinu čísel ai „pootočímeÿ o x a sečteme samu se sebou.)
0
8
1 2
7 3
6 4
5 Znázornění změn čísel ai na čísla přidáváme prvek x = 5.
a′i
pro m = 9. K množině M = {2, 7}
Učiníme teď dvě pozorování o hodnotách a′min , P ′ . Jednak si všimneme, že platí a′min ≥ amin . Tento fakt je jednoduchým důsledkem toho, že každé nenulové a′i vzniklo součtem čísel ai a ai−x , z nichž alespoň jedno muselo být nenulové. Na druhou stranu platí, že P ′ ≤ P . Pokud totiž a′i = 0, pak muselo být i ai = 0. Situaci dále rozdělíme na dva případy. (i) P ′ < P , čili P ′ ≤ P − 1: V tomto případě máme triviálně ′
a′min ≥ amin ≥ 2n−m+1+P = 2(n+1)−m+1+(P −1) ≥ 2(n+1)−m+1+P . (ii) P ′ = P : Díky předpokladu se muselo ke každému nulovému ai přičíst nulové ai−x , a tedy se ke každému nenulovému ai muselo přičíst nenulové ai−x . Tím pádem se hodnota amin alespoň zdvojnásobila, my máme a′min ≥ 2 · amin ≥ 2 · 2n−m+1+P = 2(n+1)−m+1+P = 2(n+1)−m+1+P a důkaz je u konce.
′
