The Postal Owl

1. $(\{1, ..., n\},|)$

Uvažujme, že přidáním čísla $x$ do našeho antiřetězce vyloučíme přidání jakéhokoliv násobku $x$. Přidáme-li do antiřetězce dvojku, musíme vyloučit každé sudé číslo, což je taky každé druhé číslo.

Uvědomme si, že můžeme udělat antiřetězec $\{\lfloor \frac{n}2 \rfloor + 1, ..., n\}$, kde žádné číslo nebude násobkem druhého, protože nejmenším možným násobkem, kterým by mohlo být, je dvojnásobek, a už dvojnásobek prvního členu bude větší, než člen poslední $2\cdot\lfloor \frac{n}2 \rfloor + 2 > n$.

Podívejme se na to, že tento antiřetězec musí být také nejdelší možný.

Uvažme, že bychom do takového antiřetězce přidat další prvek. Musel by to být prvek $x \leq \frac{n}2$, protože větší prvky už v antiřetězci máme. Po přidání takového prvku bychom ale vždy museli minimálně jeden prvek odebrat, protože aspoň dvojnásobek přidáného prvku už jsme v původním antiřetězci měli. Takovouto změnou si tedy nepomůžeme.

Mohlo by se stát, že více výše popsaných změn (přidání) by mohlo vést z celkově většímu počtu? Ne, protože dvě změny se buď neovlivní, se navzájem vyloučí, protože jeden přidávaný prvek bude násobkem druhého.

2. $(2^{[n]}, \subseteq)$

Použijme podobnou logiku. Vždy můžeme vytvořit antiřetězec složený ze všech $k$-prvkových podmnožin, $k \leq n$.

Největší z takovýchto antiřetězců bude pro střední hodnotu $k = \lfloor\frac{n}2\rfloor$ nebo $k = \lceil\frac{n}2\rceil$ , to vidíme na hasseově diagramu.

Když budeme mít takovýto antiřetězec, můžeme ho zkusit zvětšit tím, že přidáme nějaké množiny s méně, nebo více prvky, a ubereme nějaké množiny s $k$ prvky. Bez újmy na obecnosti si stačí uvědomit, že když přidáme jednu větší, nebo menší množinu, musíme ubrat více prvků z našeho stávajícího antiřetězce, protože každá menší množina je podmnožinou více množin stávajícího antiřetězce a každá větší má v antiřetězci více podmnožin.

> Ahoj,
> 
> je to všechno super ale chybí ti ještě řetězce. Ta úloha má 4 části a ty jsi udělal 2 z nich.

Aha, díky, nějak jsem to přehlédl:

Řetězce:   
1. Pro prvky řetězce bude platit, že každý je násobkem toho předchozího, potom bude zároveň každý násobkem jakéhokoliv jiného. Začneme nejmenším možným číslem, jedničkou, a budeme pokračovat nejmenším možným násobkem, dvojnásobkem:

$\{1, 2, 4, 8, ..., 2^{ \lfloor \log_2{n} \rfloor}\}$

2. V našem řetězci bude pro každé $k$, $k \leq n$ $k$-prvková množina jen jednou, kdyby tam byly dvě různé $k$-prvkové množiny, nebyly by vlastními podmnožinami.
Jeden takovýto řetězec by byl takovýto:

$\{ \{1\}, \{1,2\}, \{1,2,3\}, ... , \{1,2, ..., n\} \}$