Matematické Fórum

Zrovna moc se v tom nevyznám. k a x jsou konstanty? V různých n-ticích jsou ty prvky, jichž je k (resp. x) různé, nebo vždy stejné? Co označuje proměnná m v nerovnosti ? Co znamená, že nějaká k-tice pokrývá n-tici s x prvky?

Zkus možná uvést příklad s nějakými konkrétními hodnotami, ať je to srozumitelnější.

Nájsť riešenie asi nie je jednoduché. Skúsim to viac objasniť nasledovne. V prípade nejasností položte otázku prosím.

V triede je X chlapcov, K dievčat a N lavíc. Každý zo žiakov má minimálne jednu  lavicu, t.j. platí   X + K ≤ N . 
A)   Nájdite minimálny spôsob rozmiestnenia žiakov do lavíc tak, aby boli splnené
       nasledovné podmienky:
    1)  vzájomne sa vylučovali rozmiestnenia (nepočítali sa do počtu rozmiestnení), kedy  jedna skupina sedí v laviciach (chlapci alebo dievčatá)  a druhá skupina sa premiestňuje po neobsadených laviciach. 
    2) premiestňovaná skupina musí mať možnosť obsadiť všetky lavice, pričom musí byť splnená podmienka 1.
    3) za nové rozmiestnenie sa považuje , keď aspoň jeden, resp. jedna žiačka je posadená do lavice, kde už sedel niektorý z druhej skupiny žiakov.
    4) chlapci sú  si z hľadiska vzájomného rozmiestnenia rovnocenný a nezáleží na tom, ktorý kde sedí (ak prvý sedí v prvej lavici a druhý v druhej lavici, je to rovnaké  ako keby prvý sedel v druhej lavici a druhý v prvej). To isté platí pre dievčatá.

B)  Koľko je takýchto minimálnych riešení?

Príklad: A) Počet dievčat K = 2, počet chlapcov X = 1, počet lavíc N = 4.
                 Nech premiestňovanou skupinou sú chlapci !
                1. Prvé rozmiestnenie:
                   Nech dievčatá sú posadené do lavíc 1 a 2. Chlapec môže sedieť buď
                   v lavici 3, alebo 4. Považuje sa to za jedno rozmiestnenie. (Podmienka 1)
               2. Druhé rozmiestnenie:
                   2.1. Jedno dievča ostane sedieť v lavici 1 :
            2.1.1.  Druhé dievča si sadne do lavici 3
                                  Chlapec môže sedieť  buď v lavici 2 alebo 4
            2.1.2.  Druhé dievča si sadne do lavici 4
                                  Chlapec môže sedieť  buď v lavici 2 alebo 3
                         V oboch prípadoch nesplnená podmienka 2 a súčasne 1 (chlapcom
                         neobsadená lavica 1) – vyžaduje  tretie rozmiestnenie s obsadením
                        lavice 1
           2.2. Jedno dievča ostane sedieť v lavici 2 :
                        Rovnocenné s 2.1.
                 2.3. Obidve dievčatá si sadnú do lavíc 3 a 4
                       Chlapec môže sedieť buď v lavici 1 alebo 2.
                       Splnená podmienka 2 a súčasne 1 – rozmiestnenie je správne
Výsledok: Minimálny počet rozmiestnení dievčat je 2. Chlapci si potom môžu vybrať
                jednu z dvoch lavíc. 
                Prvé rozmiestnenie bod 1, druhé bod 2.3.
                Možností takýchto dvojíc rozmiestnení  je viac. V tomto prípade 3

V grafickom zobrazení: (k- sedí dievča, x- sedí resp. môže sedieť chlapec, voľnú lavicu označím ? a môže v nej sedieť chlapec )
        Možné kombinácie                                  Jedno správne rozmiestnenie
                        na lavici ? môže sedieť chlapec
lavica1    k   k   k   k   k   k   ?   x   ?   x   ?   x                           k    ?       
lavica2    k   k   ?   x   ?   x   k   k   k   k   x   ?        k    ?
lavica3    ?   x   k   k   x   ?   k   k   x   ?   k   k         ?    k           
lavica4    x   ?   x   ?   k   k   x   ?   k   k   k   k           ?    k


Príklad: B)
           Počet dievčat K = 1, počet chlapcov X = 2, počet lavíc N = 4.
                 Nech premiestňovanou skupinou sú chlapci a prvé je do lavice posadené
                 dievča!
Výsledok: Minimálny počet rozmiestnení dievčat je 3.
                Chlapci si potom môžu vyberať dve lavice z troch možných. 
                Je zaujímavé, že dievča nemusí sadnúť do jednej z lavíc  (v danom prípade
                je to lavica 4) pretože dvojica chlapcov sedela už s každým dievčaťom
                (splnenie podmienok 1 a 2).

V grafickom zobrazení (voľnú lavicu označím  ? ) :
        Možné kombinácie                                  Jedno správne rozmiestnenie
                        na lavici ? môžu  sedieť chlapci
lavica1    k   k   k   ?   x   x   ?   x   x   ?   x   x                           k    ?    ?   
lavica2    ?   x   x   k   k   k   x   ?   x   x   ?   x        ?    k    ?
lavica3    x   ?   x   x   ?   x   k   k   k   x   x   ?         ?    ?    k           
lavica4    x   x   ?   x   x   ?   x   x   ?   k   k   k           ?    ?    ?

Príklad: C)
           Počet dievčat K = 2, počet chlapcov X = 2, počet lavíc N = 4.
                 Nech premiestňovanou skupinou sú chlapci a prvé je do lavice posadené
                 dievča!
Výsledok: Minimálny počet rozmiestnení je 6.
                Min počet v prípade keď  K + X = N je =  (N nad X)
V grafickom zobrazení: (voľnú lavicu označím  ? )
Možné kombinácie sú zároveň jediným rozmiestnením
                                
lavica1    k   k   x   k   x   x                                                     
lavica2    k   x   k   x   k   x                                    
lavica3    x   k   k   x   x   k                                                
lavica4    x   x   x   k   k   k