Egy klasszikus, alaposan megvariálva

szeptember 22.
tudomány
  • Link másolása
  • Facebook
  • X (Twitter)
  • Tumblr
  • LinkedIn

264. feladvány: Ikrek a ruhaboltban

Egy ruhaboltba két úr lép be, akik ikrek, tehát azonos a méretük. Szeretnének mindketten egy pár zoknit és azonos színben egy pár kesztyűt, de azt szeretnék, hogy eltérő színeket kapjanak, hogy legalább egy kicsit elkülönbözzenek egymástól.

Az eladó hátramegy a raktárba, ahol a pamut zoknik és kesztyűk a szóban forgó méretben egy nagy ládába össze vannak öntve párosítatlanul, ráadásul három színben. A kesztyűkből van balos és jobbos, ellentétben a zoknikkal, amik teljesen egyformák. A raktárkészlet szerint 10 pár fekete, 12 pár szürke és 14 pár fehér zokni, továbbá 7 pár fehér, 8 pár szürke és 9 pár fekete kesztyű van a ládában.

Sajnos a raktárban elromlott a világítás és teljesen sötét van. Legalább hány ruhadarabot kell felnyalábolnia az eladónak ahhoz, hogy biztosan legyenek köztük a két vásárló igényeinek megfelelő párosítások? Az eladó azzal nem kíván bajlódni, hogy kitapogassa a sötétben, hogy melyik zokni és melyik kesztyű.

Tipp

Nevezzük rossz esetnek ruhadarabok olyan halmazát, amikből nem lehet kihozni a kívánt párosítást. Keressük meg a legtöbb ruhadarabból álló rossz esetet. Vegyük észre, ha egy rossz eset olyan, hogy egy adott színű ruhadarabból ki lehet rakni egy párt, akkor abból a színből az összes ugyanolyan ruhadarabot berakhatjuk a rossz esetbe, mert attól ugyanúgy rossz eset marad.

Megoldás

Könnyen belátható, hogy a legrosszabb eset az, ha mindent kihúztunk, kivéve mondjuk a 7 balos fehér kesztyűt és a 8 balos szürke kesztyűt. Persze bal helyett lehetne jobb is, a lényeg, hogy nincs se fehér, se szürke kesztyűből pár kihúzva. Így tehát kihúztuk az összes zoknit, és az összes fekete kesztyűt, de hiába mert a fekete pár kesztyű mellé nincs másik színű kesztyű párban, csak fél darabok.

Ez összesen 105 ruhadarab, amiben tehát nincs megfelelő szett az ikrek számára. Ha viszont még egy ruhát hozzáteszünk, ami csak fehér vagy szürke kesztyű lehet, akkor már lesz feketétől eltérő pár kesztyű, tehát 106 ruhadarabot kell kihoznia az eladónak. Mivel pedig összesen 120 ruhadarab van a ládában, ez azt jelenti, hogy 14 kivételével az összeset fel kell nyalábolja.

Miért ez a legrosszabb eset? Hatféle ruhacsoport van: fehér zoknik, szürke zoknik, fekete zoknik, fehér kesztyűk, szürke kesztyűk, fekete kesztyűk. Ahogy a tippben említettük, keressük a legrosszabb esetet, és ha az egyik ruhacsoportból benne van egy pár, akkor már az egész csoport is benne lehet. Ahhoz hogy az ikrek ne tudjanak felöltözni kívánságuk szerint, a hat csoportból legfeljebb négyet hozhatunk ki, a maradék kettőből pedig annyit, hogy azokból ne lehessen párt alkotni. A legrosszabb esethez meg kell tehát keresni, hogy melyek azok a csoportok, amikből a legkevesebb ruhadarab bent hagyása kell ahhoz, hogy ne lehessen párt összerakni belőlük, és ez éppen a fehér és szürke kesztyűk csoportja lesz.

Ha szereted a fejtörőket, tekintsd meg korábbi feladványainkat is! Ha megjegyzésed lenne, vagy feladványt javasolnál, írj az eszventura@qubit.hu e-mail címre! Ha pedig tetszik a rovat, akkor ezt a Vendégkönyvben kifejezésre juttathatod.

Az Ész Ventura feladványügyi rovat gazdája: Gáspár Merse Előd fizikus, kognitív kutató, társasjáték-fejlesztő és bűvész.