Üdvözlet mindenkinek! Leírom a rádiós feladatra a megoldásomat. Sajnos eléggé hosszúra sikerült: Ábrázoljuk az elemeket egy 8 csúcsú gráf pontjaival. Ha 2 csúcsot él köt össze, akkor azt a két elemet egy lépésben betettük a készülékbe. Ez alapján egy él /próbálkozás/ rossznak minősül, ha legalább egyik végpontja rossz csúcs (elem). Állítás: legalább 7 kísérletre van szükség. Először azt lássuk be, hogy 6 él esetén még nem biztos, hogy van köztük jó él. Indirekten bizonyítsunk, tfh:6 él minden esetben elég ahhoz, hogy legyen jó él! Válasszuk két részre a bizonyítást: 1. Van olyan csúcs a 8 közül,amelyből legalább 3 él indul. 2. Minden élből legfeljebb 2 él indul. 1. esetben tekintek egy olyan csúcsot, amelyből legalább 3 él indul. Legyen ez a csúcs (elem) rossz! Ekkor a hat csúcsból legalább három rossz! Ha a maradék (legfeljebb) 3 él 1-1 csúcsa rossz, úgy az összes él rossz. Ez lehetséges, mert 4 rossz elem van, és az előbb is legfeljebb 4 csúcsnak kellett rossznak lennie. Tehát ez esetben nincs biztosan jó él! 2. esetben legalább 4 olyan csúcsnak kell lennie, amelyből pontosan 2 él indul.Ellenkező esetben az élek számának maximuma (ha 3csúcsból 2, 5 csúcsból 1 él indul) 11/2 lenne, de nekünk 6 él kell. Tehát van 4 ilyen csúcs. Tekintek két olyan csúcsot, amelyből pontosan két él indul, és nem köti össze őket él. Ilyen biztosan van, mert 1 ilyen csúcsot legfeljebb 2 másik ilyen csúccsal köthetek össze, és legalább 3 másik van. Legyen a kiválasztott 2 csúcs rossz! Ekkor a hozzájuk tartozó 2-2 él rossz, tehát a 6 élből négy rossz. Ha a maradék 2 él 1-1 csúcsa rossz, akkor az összes él rossz. Ez lehetséges, mert négy rossz elem van, és most is legfeljebb 4 csúcsnak kellett rossznak lennie. Tehát ez esetben sem lesz biztosan jó él. Azaz 6 kísérlet kevés a biztos eredményhez! Most még azt kell belátni, hogy hét él esetén biztosan lesz jó él, ha megfelelően választjuk meg az éleket. Erre elégséges egy konstrukciót készíteni. Legyen a 8 csúcs A;B;...H, és legyenek AB; CD; CE; DE; FG; FH;GH; csúcsok éllel összekötve. Szintén indirekten bizonyítsunk, tfh: ki tudjuk választani a 8 csúcsból a négy rosszat, úgy, hogy a fenti 7 él között ne legyen jó! Ekkor CDE háromszögben a 3 csúcsból legalább kettő rossz, ellenkező esetben lenne a háromszögben jó él! Ugyanez igaz FGH háromszögre. Tehát C;D;E;F;G;H csúcsok közül legalább 4 csúcs rossz. Azaz a négy rossz csúcs ezen hat csúcs közt van.Tehát A és B csúcsok jók, azaz AB él jó!
Ha valakinek sikerült az ehavi utolsó B-s feladatot(ha jól emlékszem B.3671.) megoldani, szívesen megnézném, mert bajlódtam vele, de nem jött ki.
|