Uşaq bağçası#6837
Hər il uşaq bağçasında üç mehriban müəllim öz siniflərinin uşaqlarına sinifləri dəyişməyə icazə verirlər və nəticədə üç yeni sinif yaranır. Təbii ki, bəzi uşaqlar kifayət qədər böyüyür və bağçanı tərk edirlər, amma qalanlar növbəti ilə qalaraq həmin üç müəllimin arasında yenidən bölüşdürülürlər.
Müəllimlər, hətta bu prosesdə uşaqlara da söz haqqı verirlər. Uşaqlıqda dostluq tez-tez yaranıb itə bildiyindən, hər bir uşaq X digər uşaqlardan Y-ni yeni sinfində görmək istəməsinə görə sıralayır. Yəni, X, digər bütün uşaqları üçün onları necə istədiyinə dair tam sıralanmış arzu siyahısı tərtib edir — siyahıda heç bir bərabərlik yoxdu, yəni eyni dərəcədə istədiyi uşaqlar olmur, seçim tam sıralanır.
Üç müəllimi siniflərin yeni formalaşmasında qeyri-bərabər ölçülü (saylı) olma halları narahat etmir, çünki onlar birinci il başlayacaq yeni uşaqlarla siniflərini dolduracaqlar. Amma onlar öz yeni siniflərində şagirdlərin hamısının əvvəlki ildən fərqli olmasını istəyirlər — axı bir il birgə olan müəllim də bir az fasiləyə ehtiyac duyur. Bu şərtlərlə üç sinfə ən yaxşı bölgü elə olmalıdır ki, heç bir uşaq, onun üstünlük siyahısında ən yuxarı T yerdə göstərmədiyi uşaqla eyni sinifdə olmasın, burada T mümkün qədər kiçik olmalıdır. Diqqət edin ki, yeni siniflərdəki uşaqlar əvvəlki ilə tamamilə eyni ola bilər, amma fərqli müəllimlərlə!
Birinci sətir uşaq bağçasında yenidən bölüşdürülməsi lazım olan uşaqların sayını n (n ≤ 200) ehtiva edir. Uşaqlar 1-dən n-ə qədər nömrələniblər.
Növbəti n sətir uşaqları təsvir edir. i-ci sətir cari tərbiyəçinin nömrəsini (tam ədəd 0, 1 və ya 2) və n − 1 tam ədəd {1, 2, 3, ..., i−1, i+1, ..., n} müəyyən bir qaydada ehtiva edir, bu da i-ci uşaq üçün üstünlük siyahısını azalan sırada təyin edir. Siyahı tam sıralanmalıdır, bərabərlik olmamalıdır, yəni iki və ya daha çox uşağın eyni yerdə durması mümkünsüzdür.
Uşaqların üç yeni qrupa elə bölünməsi üçün mövcud olan ən kiçik qeyri-mənfi tam T ki,
heç bir uşaq köhnə qrupunda olan tərbiyəçi ilə eyni deyil
hər bir uşaq üçün yeni qrupdakı bütün dostlar üstünlük siyahısının top T-indədir.
Nümunə 1