KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

KöMaL Füzetek 1: Tálalási javaslatok matematika felvételire

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 10 November 2009.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem I. 221.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley