Ha van 11 záram és 22 kulcsom, 2-2 minden egyes zárhoz, hány kombináció lehetséges?

Hát ez így kicsit kevés infó, szerintem kissé hiányos, így több megoldást is látok. Tehát pontosítani kellene: a kérdés az, hogy hány kombináció lehetséges, vagy pedig az, hogy mennyi azoknak a próbálkozásoknak a száma, amennyivel biztosan kinyitható mind a 11 zár?

Ha az összes lehetséges kombináció száma a kérdés, akkor helyes az általad írt válasz.

Ha a kérdés az, hogy hány kombinációból lehet biztosan kinyitni, akkor csak majdnem jó. Mivel egy zárhoz két kulcs van, ezért az első zárnál 22 kulcs, de ha kihúzol 20 kulcsot és egyik sem jó, akkor a 21. kulcs biztosan jó lesz, így a 22. kulcsra már nem kerül sor. Tehát helyesen 21*20*19*18*17*16*15*14*13*12*11.

Sőt, ezutóbbit tovább is lehetne vinni: ha a helyes kulcsok megtalálása a cél, akkor miután kihúztál 20-at, a maradék 2 tuti jó, tehát csak 20-at kell húzni a helyes kulcsok megtalálásához. A második zárhoz maradt 20 kulcs, 18 kihúzása után megvan a két jó kulcs, stb, míg végül az utolsó zárnál már kulcsot sem kell húzni, hiszen csak kettő kulcs maradt, mindkettő jó kulcs. Tehát 20*18*16*14*12*10*8*6*4*2.

Két lépés:

1) Hány féle módon tudod a 22 kulcsot kettes párokba osztani?

( (a b) jelentse a alatt a b-t)

Megoldás:

(22 2)(20 2)(18 2)...(4 2)(2 2) = 22!/(2^11).

2) Egy párosítást hány féle módon tudod a 11 kulcs rendelni?

Megoldás: 11!

A kérdésre a válasz a kettó szám szorzata, azaz 22!*11!/(2^11)

#1: "Sőt, ezutóbbit tovább is lehetne vinni: ha a helyes kulcsok megtalálása a cél, akkor miután kihúztál 20-at, a maradék 2 tuti jó, tehát csak 20-at kell húzni a helyes kulcsok megtalálásához. A második zárhoz maradt 20 kulcs, 18 kihúzása után megvan a két jó kulcs, stb, míg végül az utolsó zárnál már kulcsot sem kell húzni, hiszen csak kettő kulcs maradt, mindkettő jó kulcs."

#1 szerintem arra gondol, hogy az a feladat, hogy van 22 kulcs, 11 zár, és határozzuk meg minden kulcshoz, hogy melyik zárhoz tartozik. Ekkor egy stratégia, ami garantál 21 + 19 + ... + 3 + 0 = 120-nál nem több próbálkozást az az, hogy lakatonként haladunk sorba. Az első lakatra 21 próbálkozás elég megtalálni a két kulcsot (ezt #1 elrontotta, 20 még nem elég, de 21 már igen) a másodikra 19 elég, stb, az utolsó lakatra tényleg elég 0 próbálkozás. Ez egy elég jó stratégia. Ugye minden kulcsot minden lakattal végigpróbálni 22*11 = 242 próba lenne. Ezt sikerült elfeleznie azzal, hogy már ismert lakatokat (amikhez megvan mind a 2 kulcs) már nem próbál többször, illetve hogy az utolsó kulcsokat a lakatokhoz nem próbálja ki, mert annak az eredménye ismert.

Van-e ennél jobb stratégia? Mennyit garantál az, ha kulcsonként haladunk sorba?

Hány próbálkozás a várható értéke az alábbi stratégiáknak

random1: választunk egy kulcs és lakat párost, és kipróbáljuk őket. Ha nyitja, felírjuk. Addig csináljuk, amíg nem tudjuk minden kulcshoz hogy melyik lakatot nyitja.

random2: mint az előbb, de egy kulcs-lakat párost nem próbálunk kétszer.

random3: mint az előbb, de ha egy kulcshoz már megvan a lakatja, vagy egy lakathoz a két kulcsa, akkor a kulcsot/lakatot félretesszük, nem próbáljuk többször

lakat1: megkeverjük a kulcsokat, és egy lakathoz sorba próbáljuk őket. Ha megvan a két kulcs, akkor tovább megyünk a következő lakatra. (Ez ugyanaz mint amit írtam #3-ban és #1 is próbált, csak nem a legrosszabb esetet nézzük, hanem randomizáljuk és a várható érték kell.)