Problem B. 5037. (May 2019)

B. 5037. A polyhedron \(\displaystyle P\) is divided into the smaller polyhedra \(\displaystyle P_1, \ldots, P_k\) and also divided into the smaller polyhedra \(\displaystyle Q_1, \ldots, Q_k\) such that the polyhedra \(\displaystyle P_i\) and \(\displaystyle Q_i\) are congruent for all \(\displaystyle i=1, \ldots, k\). Show that it is possible to select some points in the interior of \(\displaystyle P\) such that there are the same number of points (at least one) in the interior of polyhedra \(\displaystyle P_i\) and \(\displaystyle Q_i\) for all \(\displaystyle i=1, \ldots, k\). (The position of each polyhedron is fixed in the space.)

(6 pont)

Deadline expired on June 11, 2019.

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

Megoldás. Tekintsük \(\displaystyle P_j\) és \(\displaystyle Q_j\) poliéderek összes lapsíkjait. Darabolják ezek a \(\displaystyle P\) poliédert \(\displaystyle R_1, \ldots, R_m\) kis poliéderekre (amelyek egyfajta "közös finomításai" a \(\displaystyle P_i\) és \(\displaystyle Q_i\) feldarabolásoknak).

Jelölje \(\displaystyle x_j\) az \(\displaystyle R_j\)-be eső kijelölendő pontok számát. (A daraboló síkokra nem teszünk pontot.) Ha felírjuk az összes feltételt, miszerint \(\displaystyle P_i\) és \(\displaystyle Q_i\) poliéderekbe ugyanannyi kijelölt pont esik, akkor kapunk egy \(\displaystyle k\) darab egyenletből álló egyenletrendszert \(\displaystyle x_j\) ismeretlenekkel. Világos, hogy az egyenletrendszer homogén lineáris, és az \(\displaystyle x_j\)-k együtthatói egészek (valójában \(\displaystyle -1\), \(\displaystyle 0\) vagy \(\displaystyle 1\) minden együttható). A továbbiakban megmutatjuk, hogy ennek az egyenletrendszernek van olyan megoldása, amiben minden változó pozitív egész értéket vesz fel. Ebből a feladat állítása azonnal következik.

Először is vegyük észre, hogy az egyenletrendszernek egy pozitív megoldása, ha \(\displaystyle x_j\) éppen \(\displaystyle R_j\) térfogata. Valóban, mivel \(\displaystyle P_i\) és \(\displaystyle Q_i\) egybevágóak, így térfogatuk megegyezik. Továbbá a térfogat tulajdonságai miatt \(\displaystyle P_i\) térfogata megegyezik a bele eső \(\displaystyle R_j\) poliéderek térfogatainak összegével.

Ebből következően az egyenletrendszernek végtelen sok megoldása van, vagyis a megoldásban van legalább egy szabad változó. Továbbá mivel az egyenletrendszer egész együtthatós, így a Gauss-elimináció során végig csak racionális együtthatók fordulhatnak elő, vagyis a kötött változók kifejezhetők a szabad változók racionális együtthatós lineáris kombinációjaként. Ezek alapján világos, hogy ha a szabad változók értékét a korábban mutatott pozitív megoldásban felvett valós értékhez elegendően közeli racionális számnak választjuk, akkor olyan megoldást kapunk, amelyben minden változó pozitív racionális értékű. Ebből - kihasználva a homogenitást - a nevezők legkisebb közös többszörösével szorozva egy csupa pozitív egészekből álló megoldást nyerünk. Ezzel a bizonyítást befejeztük.

Statistics:

10 students sent a solution.
6 points:	Beke Csongor, Füredi Erik Benjámin, Nagy Nándor, Weisz Máté.
4 points:	2 students.
2 points:	4 students.

Problems in Mathematics of KöMaL, May 2019