Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I. 221. (October 2009)

I. 221. Peter and Paul are jealous twins. They very carefully share everything until both of them get exactly the same amount. This year they were given 25 birthday presents with total value less than 1000 EUR. You have to figure out whether these presents can be shared among the twins such that both get the same value.

You should solve this task with a spreadsheet application. Cells B3:Z3 contain the value of the presents, being integers. Your answer should appear in cell A1. You should not use macros or user defined functions.

The spreadsheet (i221.xls, i221.ods, ...) together with a short documentation (i221.txt, i221.pdf, ...) -- also describing the name and version number of the spreadsheet application, further a brief description of your solution -- should be submitted in a compressed file (i221.zip).

(10 pont)

Deadline expired on November 10, 2009.


Sorry, the solution is available only in Hungarian. Google translation

A megoldók három csoportba oszthatók. Néhányan dinamikus programozási feladatként (táblázatkitöltőként) értelmezték és oldották meg a feladatot. Mások megpróbálták megadni az ajándékok testvéries felosztását. Ez nem mindig járt sikerrel. Voltak, akik kihasználták a táblázatkezelő nyújtotta lehetőségeket és a Solver bővítménnyel igen egyszerű megoldást adtak. A szerzett pontszám természetesen független a megoldás módjától.

Az alábbiakban a táblázatkitöltés módszerét ismertetjük részletesen.

Akik úgy gondolják, hogy meg kell vizsgálni az összes elosztási lehetőséget a kérdés megválaszolásához, nem veszik figyelembe, hogy az ajándékok elosztását nem, csak az eloszthatóságát kell megadnunk. Ebben az esetben viszont nem kell megkülönböztetnünk az ajándékokat és elegendő csupán annak értékével dolgoznunk.

Csak azzal a nemtriviális esettel foglalkozunk érdemben, ahol az ajándékok összértéke páros.

Ha meg tudjuk határozni, hogy milyen értékben kaphatott ajándékot egyikük, lényegében megoldottuk a feladatot. Ugyanis könnyen belátható, hogy ha az értékek között szerepel az ajándékok összértékének fele, akkor az ajándékok egyenlő értékben eloszthatók.

Vegyük észre, hogy nincs is szükség az összes lehetséges értékre. Elegendő, ha 500-ig meghatározzuk (csak egyikük ajándékaival törődünk), hiszen az összérték 1000-nél nagyobb nem lehet.

Oldjuk meg a feladatot lépésről lépésre haladva, azaz határozzuk meg, hogy az első k ajándékból hogyan részesülhetett egyikük. Ehhez az ajándékok sorrendjét rögzíteni kell, de a sorrend a végeredmény - az összes elosztása - szempontjából nem lényeges.

Ennek meghatározására egy 501 soros és 26 oszlopos segédtáblát használunk. A segédtábla i. oszlopának j. sora azt jelzi, hogy az egyik testvér i darab ajándék eloszltását követően kaphatott-e j értékben ajándékot. Ha kaphatott, jelöljük IGAZ, egyébként HAMIS értékkel.

A 0. oszlopban - lévén egyetlen ajándékot sem osztottunk ki - a 0. sor kivételével HAMIS érték szerepel. Ez fejezi ki, hogy 0 értékben kaphatott ajándékot.

Alkossunk egy másolható képletet, amely a nagyobb (mint 0) oszlopszámokra a teljes tartományon belül szabadon másolható. Az i. oszlop j. sorának kitöltésénél két esetet kell megvizsgálnunk: az adott testvér megkapta-e az ajándékot vagy sem.

(1) Ha nem kapta meg, akkor a j. cella értéke csak akkor lehet igaz, ha j értékben kaphatott az első i-1 ajándékból.

(2) Ha megkapta az i-edik ajándékot, és annak értéke E(i), akkor a j értékben csak úgy juthat ajándékhoz, ha az első i-1 ajándékból j-E(i) értékben részesülhetett.

Ha ezt a teljes segédtáblára megfogalmazzük, akkor az utolsó oszlop megfelelő cellájának értéke megadja, hogy a feladat kérdésére a választ. A kérdéses cella a j=[ajándékok összértéke]/2.

A mintaként adott megoldásban a segédtáblát az A5:Z505 tartományban felvéve a következő értékeket használjuk:

A5=IGAZ A6:A505=HAMIS

B5 érékét egy függvénnyel adjuk meg, amelyet a teljes B5:Z505 tartományba átmásolhatunk.

B5=VAGY(A5;HA(SOR()-B$3>4;INDEX(A$5:A$505;SOR()-B$3-4)))

A logikai függvény első paramétere az (1), a második pedig a (2) esethez tartozik.

Figyelem, újabb sorok beszúrásával a B5:Z505 tartomány celláinak értéke módosításra szorul.

A választ az A1-es cellában kell előállítani.

Ehhez az A3 cellában meghatározom az ajándékok összértékét. A3=SZUM(B3:Z3)

Az előállíthatósághoz szükséges, hogy az összeg páros legyen és a segédtábla utolsó oszlopában az ajándék összértékének felét adó sorban IGAZ érték szerepeljen.

A1=HA(ÉS(MARADÉK(A3;2)=0;INDEX(Z6:Z505;A3/2));"Igen";"Nem")


Statistics:

7 students sent a solution.
10 points:Balla Attila, Gaizer Bence, Paróczi Gergő.
8 points:1 student.
5 points:1 student.
3 points:1 student.
2 points:1 student.

Problems in Information Technology of KöMaL, October 2009