Co jsou ZKRÁCENÉ ROZPISY

Matematické jádro zkráceného rozpisu

Zkrácený rozpis není „tajný trik“, ale kombinatorická konstrukce. Máme v vybraných čísel, z nich skládáme sloupce velikosti k a chceme, aby každá kombinace velikosti t byla obsažena alespoň v jednom sloupku.

Značení

v = počet vybraných čísel
k = počet čísel v jednom sloupku
t = velikost kombinace, kterou chceme jistě pokrýt

Typická otázka zní: Kolik nejméně sloupců potřebujeme, aby byla každá t-kombinace pokryta alespoň jednou?

Základní vzorce

Počet všech požadovaných t-kombinací

C(v,t) = v! / ( t! · (v−t)! )

Jeden sloupec velikosti k pokryje

C(k,t)

Dolní odhad na počet sloupců

N ≥ ceil( C(v,t) / C(k,t) )

Toto je teoretické minimum. Někdy je dosažitelné přesně, jindy nikoli.

Steinerův systém = ideální případ

Pokud existuje konstrukce, ve které je každá požadovaná t-kombinace pokryta právě jednou, mluvíme o Steinerově systému označovaném S(t,k,v).

To je „dokonalý rozpis“: nic nechybí a nic se zbytečně neopakuje.

Příklad 1: jak se dvojice skládají do trojic

Vezměme 7 čísel. Chceme, aby každá dvojice byla obsažena v některé trojici. Tedy:

Parametry

v = 7, k = 3, t = 2

Všech dvojic

C(7,2) = 21

Jedna trojice obsahuje

C(3,2) = 3 dvojice

Teoretické minimum

N ≥ ceil(21 / 3) = 7

Zde nastává krásný případ: přesná konstrukce opravdu existuje. Jde o Steinerův systém S(2,3,7), nazývaný také Steiner triple system řádu 7.

123

145

167

246

257

347

356

Těchto 7 trojic pokryje všech 21 dvojic právě jednou. To je ideální situace bez plýtvání.

Příklad 2: loterijní rozpis pro Sportku

Vyberete 10 čísel. Jeden sloupec má 6 čísel. Chcete mít jistotu, že pokud z Vaší desítky padnou jakékoli 3 správné čísla, budou spolu alespoň v jednom sloupku.

Parametry

v = 10, k = 6, t = 3

Všech trojic

C(10,3) = 120

Jedna šestice obsahuje

C(6,3) = 20 trojic

Dolní odhad

N ≥ ceil(120 / 20) = 6

Na první pohled by se zdálo, že by mohlo stačit 6 sloupců. To by však odpovídalo přesnému Steinerovu systému S(3,6,10). Ten ale neexistuje.

Proč neexistuje?

Nutná podmínka pro Steinerův systém mimo jiné vyžaduje, aby výraz

C(v−1, t−1) / C(k−1, t−1)

vyšel jako celé číslo. Zde tedy:

C(9,2) / C(5,2) = 36 / 10 = 3,6

což celé číslo není. Proto ideální přesná konstrukce neexistuje a skutečný rozpis musí být typu covering design, tedy s více překryvy a obvykle s více než 6 sloupci.

To je přesně důvod, proč v praxi často nehledáme „dokonalý“ rozpis, ale co nejlepší dosažitelný rozpis.

Co je covering design

Pokud Steinerův systém neexistuje, přecházíme k praktičtější variantě: covering designu. Jeho cílem není pokrýt každou t-kombinaci právě jednou, ale alespoň jednou.

Steinerův systém

každá t-kombinace právě jednou
žádné zbytečné překryvy
matematicky ideální případ
neexistuje pro všechny parametry

Covering design

každá t-kombinace alespoň jednou
překryvy jsou povolené
prakticky použitelný v reálných úlohách
hledáme co nejmenší počet sloupců

Reálný zkrácený rozpis je tedy zpravidla covering design: některé t-kombinace se mohou objevit vícekrát, ale žádná z požadovaných kombinací nesmí zůstat nepokrytá.

Jak se z dvojic a trojic staví vyšší k-tice v praxi

Praktická konstrukce rozpisu často začíná na nižší úrovni: sledujeme dvojice nebo trojice, které chceme pokrýt, a ty pak skládáme do větších bloků, tedy do vyšších k-tic.

2-prvkové vazby

dvojice

např. 12, 17, 39

→

3-prvkové bloky

trojice

1 trojice obsahuje 3 dvojice

→

6-prvkové sloupce

šestice

1 šestice obsahuje 20 trojic a 15 dvojic

Z kombinatorického hlediska je to velmi silné: větší blok pokryje mnoho nižších struktur najednou. Například jedna šestice obsahuje:

Počet dvojic v jedné šestici

C(6,2) = 15

Počet trojic v jedné šestici

C(6,3) = 20

Praktický význam

1 blok kryje mnoho nižších vazeb

Proto se v praxi často nepracuje jen s jednotlivými sloupci „od oka“, ale s cíleným skládáním nižších k-tic do vyšších bloků tak, aby se pokrytí rozložilo co nejrovnoměrněji.

V loterijní praxi to znamená, že konstrukce rozpisu není jen „výběr několika sloupců“, ale pokus rozmístit nižší kombinace do vyšších bloků co nejúčelněji. Právě v tom spočívá odbornost zkrácených rozpisů.