Šest sekcí konference: rozvrh pod omezeními
Studentská konference má šest sekcí, každá proběhne právě jednou, v šesti po sobě jdoucích blocích označených 1 až 6. Sekce: Angličtina (A), Biologie (B), Chemie (C), Dějepis (D), Ekonomie (E), Filozofie (F). Organizátoři stanovili pět pravidel: (1) Angličtina probíhá bezprostředně před Biologií. (2) Chemie probíhá dříve než Dějepis. (3) Ekonomie není ani první, ani poslední. (4) Filozofie je třetí. (5) Ekonomie probíhá dříve než Filozofie. Studenti si stěžují, že v rozvrhu nedokážou najít pořadí, které by všechna pravidla splňovalo, a šíří mezi sebou různé verze. Vaším úkolem je rozvrh prověřit. Žádná sekce se nekoná dvakrát a mezi bloky nejsou přestávky, které by pořadí měnily. Pořadatelé trvají na tom, že každé pravidlo musí platit současně s ostatními.
1. Která sekce může být v prvním bloku? Určete to a zdůvodněte vylučovacím postupem.
Read the worked answer
První může být pouze Chemie.
Krok 1: Z pravidla (5) E < F a z pravidla (4) F = 3 plyne, že E je v bloku 1 nebo 2. Pravidlo (3) vylučuje blok 1, takže E = 2 a F = 3.
Krok 2: Volné jsou bloky 1, 4, 5, 6 pro A, B, C, D. Pravidlo (1) vyžaduje, aby A a B byly hned po sobě. Dvojice (1,2), (2,3) a (3,4) nepřipadají v úvahu, protože bloky 2 a 3 jsou obsazené. Zbývají (4,5) a (5,6).
Krok 3: V obou případech zůstávají pro C a D jen bloky z množiny {1, 4, 5, 6}, a to tak, že C musí být před D (pravidlo 2).
- Při A, B na (4,5) zbývá C, D na (1,6) → C = 1, D = 6.
- Při A, B na (5,6) zbývá C, D na (1,4) → C = 1, D = 4.
V obou případech je tedy C = 1. Blok 1 nemůže obsadit nikdo jiný: A ani B nemohou být první (potřebují předchůdce), E být první nesmí a F je pevně třetí.
Odpověď: Chemie (C).
2. Kolik přípustných rozvrhů existuje? Vyjmenujte je a u každého ověřte všech pět pravidel.
Read the worked answer
Existují právě dvě přípustná pořadí:
| blok | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| varianta I | C | E | F | A | B | D |
| varianta II | C | E | F | D | A | B |
Kontrola obou variant:
- (1) A hned před B: v I je to 4→5, v II 5→6. ✓
- (2) C před D: v I 1 < 6, v II 1 < 4. ✓
- (3) E není první ani poslední: v obou je E = 2. ✓
- (4) F = 3. ✓
- (5) E před F: 2 < 3. ✓
Proč nic jiného neexistuje: E = 2 a F = 3 je vynuceno. Pro A, B zbývají jen dvojice (4,5) a (5,6), protože (1,2), (2,3) a (3,4) kolidují s obsazenými bloky. Každá z těchto dvou možností pak jednoznačně určí pozice C a D. Počet řešení je tedy 2 × 1 = 2.
Poznámka: úloha není nedourčená. Dvě řešení nevznikla chybějící informací, ale tím, že pravidla připouštějí právě dvě možnosti. Rozdíl je důležitý: kdyby se organizátoři ptali „které pořadí je správné“, museli by dodat další pravidlo.
3. K původním pěti pravidlům se přidá pravidlo (6): Dějepis probíhá dříve než Angličtina. Co z toho pro rozvrh plyne?
Read the worked answer
Přidáním pravidla (6) zůstane jediné řešení: C, E, F, D, A, B.
- Varianta I (C, E, F, A, B, D): D = 6, A = 4, tedy D > A → pravidlo (6) nesplňuje.
- Varianta II (C, E, F, D, A, B): D = 4, A = 5, tedy D < A → splňuje.
Závěr: rozvrh je nově určen jednoznačně - Chemie, Ekonomie, Filozofie, Dějepis, Angličtina, Biologie.
Poznámka k metodě: nové pravidlo nemění nic na tom, co už bylo odvozeno (E = 2, F = 3, C = 1). Proto stačí prověřit jen dvě zbývající varianty. Kdybych začínal znovu od nuly, ztratil bych čas a hrozilo by, že mi některá varianta unikne.
Zobecnění: přidání podmínky může počet řešení snížit, ale nikdy ne zvýšit. Pokud by po přidání pravidla (6) zůstala dvě řešení, znamenalo by to, že pravidlo je s původními podmínkami slučitelné ve více bodech, a museli bychom hledat další rozlišující údaj.