Találós kérdés ajándékokról - Megoldás

Day 4,080, 03:04 • Published in Hungary Hungary • by align

Múlt héten az alábbi kérdést tettem fel.

Három játékos egymás között szeretné elcsereberélni a még meglévő ajándékaikat. Méghozzá az összeset, és természetesen úgy, hogy mindenki ugyanannyit kapjon, mint amennyit küld. Pontosan mikor sikerülhet ez?
(Jelölje mondjuk a, b, c az elküldhető ajándékaik számát.)



Megoldás

A játékosokat A-nak, B-nek és C-nek hívom, akiknek (ebben a sorrendben) a, b és c darab ajándéka van. Azt is feltehetjük, hogy A-nál senkinek nincs több ajándéka, és B-nek is legalább annyi van, mint C-nek:
a >= b => c.

Ha A-nak pontosan annyi ajándéka van, mint B-nek és C-nek összesen, vagyis a=b+c, akkor van megoldás: ekkor B és C is A-val cserél ajándékokat, külön-külön.

Ha A-nak több ajándéka van, mint B-nek és C-nek összesen, akkor A nem tud annyi ajándékot kapni, mint amennyit ő küld, még akkor sem, ha B és C mindenüket A-nak küldik. Tehát a megoldáshoz biztosan szükséges, hogy
b + c >= a.

Ez az úgynevezett háromszög-egyenlőtlenség (bár háromszögekre inkább úgy szól, hogy a háromszög bármely oldalának hossza kisebb mint a másik két oldal hosszainak összege).

Azt fogjuk belátni, hogy a b + c >= a feltétel elégséges is, vagyis amikor ez teljesül, akkor valóban van megoldás.

Először egy másik különleges esetet nézzünk meg: amikor A-nak, B-nek és C-nek pontosan ugyanannyi ajándéka van, vagyis a=b=c. Ekkor is van megoldás: A mindent B-nek küld, B mindent C-nek küld, C mindent A-nek küld.

Most akkor nézzük azt az esetet, amikor b + c >= a teljesül, vagyis A-nak legfeljebb annyi ajándéka van, mint B-nek és C-nek összesen. És persze továbbra is feltesszük, hogy a>=b>=c.

1. Először A cseréljen B-vel annyi ajándékot, hogy B-nek ugyanannyi ajándéka maradjon, mint C-nek. Még ekkor is A-nak marad a legtöbb (vagy egyik legtöbb) ajándéka.

2. Ha A-nak, B-nek és C-nek pontosan ugyannyi ajándéka van, akkor készen vagyunk, mert körbe adhatják őket, mint a fenti példán láttuk.

3. Ha viszont A-nak több van, mint B-nek (vagyis C-nek), akkor A cseréljen B-vel és C-vel is egy-egy ajándékot. Ezzel a lépéssel A ajándékainak száma kettővel csökken, míg B és C ajándékainak száma eggyel.

4. A 3. lépést ismételgessük egészen addig, amíg A-nak, B-nek és C-nek pontosan ugyaannyi ajándéka nem lesz, ezután a 2. lépéssel kész.

Rövid megoldás
Ha b + c >= a, akkor:
- A cseréljen B-vel a-c darab ajándékot, és
- A cseréljen C-vel a-b darab ajándékot.
Ezután A-nak, B-nek és C-nek pontosan ugyanannyi, b+c-a darab ajándéka marad, amely nemnegatív, tehát tényleg tudnak ennyit cserélni. Ezután körbeküldik az ajándékokat valamelyik irányba.

Konkrét megoldás
Ha b + c >= a, akkor
A küld b darabot B-nek,
A küld a-b darabot C-nek,
B küld a-c darabot A-nak,
B küld b+c-a darabot C-nek,
C küld c darabot A-nak.
Ekkor mindenki mindenét elküldte, és pontosan annyit is kapott vissza (és minden itt szereplő mennyiség nemnegatív).

Szükséges-e, hogy a+b+c páros szám legyen?

Nem szükséges, hiszen fent már megoldottuk a feldatatot ezen feltétel nélkül is. De ha ragaszkodunk hozzá, hogy a három játékos között csak kölcsönös cserék lehetnek, tehát pl. B ugyanannyit kell küldjön A-nak, mint amennyit A küld B-nek, akkor pontosan akkor van megoldás, ha
b + c >= a (tehát senkinek nincs több ajándéka, mint a másik két játékosnak összesen),
és a+b+c páros szám.
Ennek meggondolását az olvasóra bízom.

Eredményhirdetés

Helyes és lényegében helyes megoldásokért jutalomban részesült Hgmg, fsb1000, Raab Donat és baramis.

Bónusz feladat (amely azért vitathatatlanul sokkal kevésbé érdekes)

Ha az egyik játékosnak 100, a másiknak 80, a harmadiknak 60 ajándéka van, akkor hányféleképpen tudják egymás között elcserélni őket? (A küldés sorrendje ne számítson, csak az, hogy az egyes játékosok összesen mennyit küldenek egyik illetve másik játékostársuknak. Nem kell, hogy kölcsönös cserékből álljon a megoldás.)
A leggyorsabb helyes válaszoló még kap tőlem egy ajándékot.