54. Rajzoljuk be a (0,1) intervallumba az a/p és a b/q alakú pontokat (0<a<p és 0<b<q egész). Ez az intervallumot p+q–d részintervallumra osztja, s ha a tortát sorra olyan darabokra vágjuk, mint az egyes, így keletkezett intervallumok hossza, akkor nyilván egy megfelelő vágást kapunk p+q–d részre. Másrészt osszuk fel a tortát a feladat feltételeinek megfelelő módon. Tekintsük azt a páros gráfot, amelynek “fent” p pontja, “lent” q pontja van; a fenti pontok azok a halmazok, amelyeket az egyes vendégek kapnak, ha p egyenlő részre osztjuk a tortát, a lenti pontok azok a halmazok, amelyeket az egyes vendégek kapnak, ha q részre osztjuk a tortát. Két pont akkor van összekötve, ha a két halmaznak van közös eleme. (A felső i-edik pont és az alsó j-edik pont akkor van összekötve, ha az i-edik vendég a p-ből és a j-edik vendég a q-ból legalább egy azonos tortaszeletet kapna.) Ha d=1, akkor ez a gráf összefüggő. Ha ugyanis fentről a, lentről b pont alkot egy komponenst, akkor vegyük a pontoknak megfelelő a illetve b embert. Ez az a ember csak olyan tortarészeket kapna a p-es felosztásnál, amilyeneket a b másik kapna a q-as felosztásnál. Ez viszont azt jelenti, hogy az a embernek járó a/p rész és a b embernek járó b/q rész egyenlő. Vagyis aq=bp. Ha most p és q relatív prímek, akkor p|a>0 és q|b>0, vagyis a≥p és q≥b, tehát a=p, b=q, és ez pontosan azt jelenti, hogy a gráf összefüggő (csak egy komponensből áll). Ha viszont (p,q)=d, és p=dP, q=dQ, akkor P|a, Q|b, tehát a≥P=p/d, b≥Q=q/d, amiből viszont következik, hogy a gráf legfeljebb d komponensből áll, vagyis legalább p+q–d éle van. Ez azt jelenti, hogy legalább p+q–d részre vágtuk a tortát (minden él legalább egy tortaszeletet jelent, különböző élek különböző tortaszeletet jelentenek).
TARTALOMJEGYZÉK |