Задача 3

Време е за задача номер 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)
Дадени са два еднакви набора от пулове и от тях са сглобени две редички, които започват и завършват с еднакви точки. Да се докаже, че с разрешената операция от едната можем да получим другата.

Наслука.

Недев, уточни какво имаш предвид под:
"две редици... които започват и завършват с еднакви точки" Сещам се за три варианта. Примерно:
1) Първата започва с 1 и завършва с 1 И втората започва с 1 и завършва с 1
2) Първата започва с 1 и завършва с 1, втората започва с 2 и завършва с 2
3) Първата започва с 1 и завършва с 2 И втората започва с 1 и завършва с 2.

spored men e 2)

А пък според мен е 3). Като се замислиш, при 2 задачата няма смисъл - всяка операция запазва точките в началото и края. 1)... Не, мисля че е 3).

iskah da kaja 'spored men NE e 2)'
izviniavam se za greshkata

ne vijdam osobena razlika mejdu 1) i 3) /osven che spored 1) vsichki chisla zaduljitelno se sreshtat po cheten broi puti/

znachi, ako sum razbrala pravilno - zadachata e da se dokaje che s vaprosnata operacia moje da se podredi koia da e kombinacia na domino redica (ot edni i sashti elementi) s fiksirani kraishta (no ne i elementi)

Мдаааа, ако случайно РЕШИШ да се регистрираш, ще можеш да си редактираш мнението след като си го постнала.

znam :) - no pak niamashe da go popravia - burzah /za rabota/

vaprosut koito povdigash ima oshte 2 strani
1) po moe lichno super subektivno mnenie niama po-goliama svoboda ot svobodata da si neizvesten (ottuk i psevdonima koito polzvam)
2) tova s popravkite ne mi haresva - kraino vreme mi e (lichno na men) da se naucha da ia karam bez popravki - tolkova sum razseiana che napravo si e strashno. ako shte da se izlagam kato kifladjiika (btw ne se znae znae li se dali ne si izkarvam hliaba s pechene na kifli taka ili inache )

.edno momiche

Towa moze bi njama znachenie, no wse pak: Kombinaciata (x,y) samo wednyz li se sreshta wyw wseki nabor plochki?

ako vsichki plochki sa razlichni - kak mislish, kolko kombinacii ot domino verijki shte mojesh da imash (s fiksirani kraishta)?

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

Pyrvo, izvinenia, no dnes (ne dai si boze OT dnes) shte pisha na latinica.
Po zadachata: Spored men zadachata ne e otvratitelna, otvratitelno ti e reshenieto:))). Oshte ne sym go shvanal dokrai, zatova pyrvo shte ti napisha moeto.
I taka, da predpolojim che pyrvata redica pochva s 1
1,a1|a1,a2|....|a(n-1),an
Neka vtorata da e
1,b1|....|b(n-1),bn(=an)
Pravilno si otbeliazala, che vyv vtorata redica plochkata 1,a1 triabva da e orientirana po syshtia nachin kato v pyrvata, inache s edno obryshtane ia dokarvame nai-otpred i posle puskame indukciata. Znachi vtorata redica izglejda taka:
1,b1|...|1,a1||a1,b(k+1)|...|b(n-1),bn(=an)
Tuka e vreme da dopusnem protivnoto, a imenno che plochkata 1,a1 ne moje nda byde dokarana nai-otpred. Ot tova v chastnost sledva, che plochkata nikoga ne moje da byde obyrnata. Ottuk sledva, che niama tochki predi plochkata, koito da syvpadat s tochki sled plochkata (inache sha fanem podredichkata i sha ia obyrnem). Da narechem uslovno tochkite predi plochkata malki, a tezi sled - golemi. Togava praim izvoda che EDINSTVENATA plochka ot vida malko-goliamo e 1,a1. togava, vryshtaiki se na pyrvata redica - da napomnim:
1,a1|a1,a2|....|a(n-1),an
pravim generalnia izvod, che pyrvata edinica sa edinstvenite malki tochki v nabora ot plochki. Da prodyljavam li natatyk?

ne smiatam che tova reshenie e po-neoburkvashto ot moeto - kakto i che ima niakakva razlika vaobshte - az prosto sum go razpisala, a ti si go izfilosofstval - principa e sashtia - vzemame edna 'malka' plochka' i dokazvame che (1,a1) moje da se oburne

osven tova sum sigurna che ako go biah napisala taka - sas filosovstvane - pak niamashe da ti haresa

edna zabelejka - bn!=an

i da, zadachata e otvratitelna.

.edno momiche

И двете решения са правилни. Просто Недев не прави нищо повече от необходимото - доказва че няма как да не стане, а ти обясняваш как точно става:))) Затова и неговото е по-кратко
Така или иначе вярното решение си е вярно решение.

tochno taka - na Nedev moje i da ne mu haresva, no dokato ne nameri greshka v reshenieto mi - rezultata e 8:(5+4) v polza na Paliacho, i to pri polojenie che mu be daden avantaj i za dvete zadachi (osobeno za purvata)

ne che imam neshto protiv - mnogo ste mi sladki, no ne chak tolkova che da stavam posred nosht za da si igraia s vas

.edno momiche

p.s. veroiatno Nedev shte kaje 'da be da sigurno' no purvonachalnite mi razsujdenia (sled kato se otkazah da izchisliavam kombinaciite) biaha pochti kato negovite - prosto reshih che taka dokazatelstvoto e po-strogo

Prisyzda ti se nagradata za reshenieto, razbira se. Niama da izpadam v sporove dali tvoeto reshenie e ABSOLIUTNO syshtoto kato moeto, no si ostavam s osobeno mnenie. za po-strogoto dokazatelstvo - nali znaesh che po-podrobno ne e zadylwitelno po-strogo. V chastnost, mislia che moeto e po strogo, dokolkoto pri pochti lipsvashti indexi niama kak da ima greshka ili dvusmislie v tiah. Dylgogodishnia mi opit pokazva, che tvoeto reshenie na olimpiada po matematika niamashe da gushne pylnia broi tochki. Kakto i da e - kakto spomenah - tozi pyt ti dade pyrva viarno reshenie. sledva Zadacha 4 (v nova tema).

dokato ne namerish greshka v reshenieto ne mojesh da tvurdish che niama da vzeme max broi tochki:-). ot druga strana az vijdam dvusmislie v tvoeto obiasnenie, no niamam namerenie da go raznishtvam, zashtoto moje da se popravi mnogo lesno

znachi tova sa olimpiadski zadachi, taka li? breh

Tebe iavno ne sa te riazali po olimpiadi deto da se chudish otkyde ti e doshlo... Ako si mislish che rejat samo za greshki. A zadachkite sa olimpiadski, obache v imeto na systezanieto tuk, molia ne tyrsete otkude sa.