Úkoly z diskrétní matematiky, 1. série

Veškerá tvrzení precizně zdůvodněte.

(1.1) Určete součet řady

∑_{i=0}^{n−1}(2i + 1),

neboli součet prvních n lichých přirozených čísel. Nezapomeňte podrobně zdůvodnit (resp. dokázat), jak jste došli k výsledku. 2 body

(1.2) Nechť X a Y jsou dvě množiny (úplně libovolné). Poctivě formálně dokažte,

že

X = Y ⇔ 2^{X} = 2^{Y} .

Výrazem 2^{X} rozumíme množinu všech podmnožin množiny X. 3 body

(1.3) Máte navrhnout sadu závaží na rovnoramenné váhy. Na levou misku se položí předmět s celočíselnou váhou od 1 do n, na pravou misku závaží, misky se musí vyrovnat. Na cvičení jsme si zdůvodnili, že jako závaží dobře poslouží mocniny dvojky. Určete přesný vzorec v závislosti na n, kolik minimálně těchto závažícek potřebujeme k odvážení předmětů. Dále dokažte, že nemůže existovat co do počtu menší sada, která by odvážila všechny předměty, a to ani když povolíme jiné hodnoty, než mocniny 2. 3 body