Време е за задача номер 3. Като малък реверанс към едно момиче (и извинение че я поствам толкова рано) тази е с трудност 8.
Задача 3(Трудност 8)
С известно количесто пулове за домино е построена редичка по стандартните правила (чрез долепяне на еднакви точки). С парче от редицата, имащо в двата си края еднакви точки е разрешено да се направи следното - хващаме парчето, обръщаме го наобратно и го лепим на мястото му. Например
(1,3)|(3,3)(3,5)(5,6)(6,3)|(3,2) -> (1,3)|(3,6)(6,5)(5,3)(3,3)|(3,2)
или
(1,2)(2,4)(4,4)(4,1)|(1,6) ->(1,4)(4,4)(4,2)(2,1)|(1,6)
Дадени са два еднакви набора от пулове и от тях са сглобени две редички, които започват и завършват с еднакви точки. Да се докаже, че с разрешената операция от едната можем да получим другата.
Наслука.
|
Neka redicata-model da e
A: (a,b),..,(op),(pq),..,(uv)
(1),.. ,(k-1),(k),.. ,(n)
a redicata za preobrazuvane
B: (ax),..,(wv)
(1),.. ,(n)
1) Neka B1 != A1 - t.e. x != b . Togava plochka A1 (a|b) se namira niakude po-natatuk po (B) domino verigata:
(ax),..,(A1),...
1.1) Ako A1 e 'oburnata' -> = (b|a), to togava B izglejda taka :
(ax),..,(ba),.. - prosto gi obrushtame, zaedno sas vsichki elementi mejdu tiah i produljavame sas sledvashtia element ot B, po indukcia
1.2) Ako obache A1 ne e 'oburnata' -> (a|b), togava B izglejda taka:
(R1) (ax),..,(ab),..
Neka k e takova, che Ak /aka (pq)/ da e parvata plochka ot (A) koiato ne se namira sled (ab) vav (B). Ako elementa-plochka tochno predi nego vav veriga (A) e Ak-1 /aka (op) {podobno na Oops - kernel fault ama ne savsem}/ - to toi se namira sled (ab) vav veriga (B) hehe
(R1->R2) (ax),...,Ak,..,(ab),..,Ak-1,..
Togava sa vazmojni slednite sluchai, spored tova dali sa oburnati Ak i Ak-1:
1.2.1)
(R21) (ax),...,(pq),..,(ab),..,(op),..
Obrushtame elementite mejdu Ak i Ak-1, koeto obrushta (ab) na (ba),:
-----> (ax),...,(po),..,(ba),..,(qp),..
i obrushtame elementite mejdu (ax) i (ba)
-----> (ab),..,(op),..,(xa),..(qp),..
/(xa)(xa)(xa) /
1.2.2)
(R22) (ax),...,(pq),..,(ab),..,(po),..
Neka elementa tochno predi (po) v tazi veriga da e primerno (zp):
-----> (ax),...,(pq),..,(ab),..,(zp),(po),..
Obrushtam redicata mejdu (pq) i (zp), koeto mi obrushta (ab) -> (ba)
/(ax)(ax) (edno) (momiche) (na) (poveche) (kafeta) (otkolkoto) (triabva)/
1.2.3)
(R23) (ax),...,(qp),..,(ab),..,(op),..
-----> (ax),...,(qp),(pz),..,(ab),..,(op),..
Obrushtam mejdu (pz) i (op) => (ab)->(ba)
/(opa)(paliacho)(zpi)/
1.2.4)
(R24) (ax),...,(qp),..,(ab),..,(po),..
-----> (ax),...,(qp),(pz),..,(ab),..,(yp),(po),..
Obrushtam mejdu (pz) i (yp) => (ab)->(ba)
2) Neka B1 == A1 - t.e. x == b . Togava vzemam smelo B2, i produljavam po goreopisania put...
Otvratitelna zadacha Nedev. okolo 2 chasa se opitvah da smetna kombinaciite na verigata predi da polucha glavobolie i da se otkaja i da probvam indukcia, da ne govorim kolko se omotah dokato go napisha tuk. Suznatelno sum slojila nomeracia navsiakude, da mi e lesno da se popraviam kato /shtoto veroiatno shte se/ naloji
.edno momiche
|