UKTG Riešenie bonusovej úlohy č. 2

Zhrnutie prednášky

Riešenie bonusovej úlohy o rozsadení N manželských párov okolo okrúhleho stola slúži ako ukážka postupu, ako sformalizovať pojem. Najprv sa úloha názorne vyskúša na malom prípade N = 3 a rozsadenia sa zapisujú lineárne. Potom sa rozsadenie definuje ako bijekcia z množiny miest Z_2N = {0, …, 2N−1} do množiny mužov a žien, pričom podmienka, že manželia sedia vedľa seba, sa vyjadrí cez inverznú funkciu a rozdiel čísel stoličiek modulo 2N, ktorý musí byť ±1. Rotácie sa následne zohľadnia reláciou ekvivalencie: dve rozsadenia sú rovnaké, ak sa jedno dá otočiť na druhé. Hľadaný počet je potom počet tried ekvivalencie tejto relácie.

• - Pri tvorbe definície je dobré si pojem najprv vyskúšať na malom príklade (N = 3).
• - Definíciu treba sformulovať pred výpočtom a nemá závisieť od spôsobu počítania.
• - Rozsadenie je bijekcia z miest Z_2N do množiny mužov a žien.
• - Podmienka, že manželia sedia vedľa seba: rozdiel čísel ich stoličiek je ±1 modulo 2N.
• - Rovnosť rozsadení až na otočenie sa zavedie reláciou ekvivalencie s rotáciou R ∈ Z_2N: g(i) = f((i + R) mod 2N).
• - Hľadaný počet rozsadení je počet tried ekvivalencie tejto relácie.

Zhrnutie pripravené s pomocou AI z prepisu videa.