Rosvojen lukot

Tämäpä ratkesikin helposti pienen tietokoneohjelman (bittipyörittelyä FORTRANilla) avulla. Enpä nyt kerro kuitenkaan vielä omaa vastaustani, jotta muutkin saavat nautiskella ongelman ratkaisemisesta.

Hyvä pieni harjoitustehtävä vaikkapa niille opettajille, jotka parhaillaan valmistautuvat perehdyttämään oppilaitaan koodauksen saloihin.

Ei tullut muita kuin Sinisalon vastaus joten kerrotaan miten oikea ratkaisu voidaan päätellä. Vaatimuksena on siis ettei mikään rosvokaksikko saa ovea auki mutta mikä tahansa rosvokolmikko saa sen auki.

Lähdetään liikkeelle mahdollisista rosvokaksikoista, joita on 10 kpl, C(5,2). Voidaan päätellä että lukkojakin tulee olla vähintään yhtä monta, yksi lukko kullekin rosvoparille jota se ei saa auki. Jos lukkoja olisi vaikkapa yhdeksän, joko yksi kaksikko saisi kaikki lukot auki tai kaksi eri kaksikkoa ei saisi yhtä lukkoa auki. Mutta silloin näistä kahdesta kaksikosta voitaisiin muodostaa kolmikko joka ei saa myöskään tuota lukkoa auki.

Avainten jako menee helpoimmin niin että ajatellaan ensin kaikille rosvoille jaettavaksi yksi kpl kaikkia avaimia. Sitten kaksikko kerrallaan poistetaan kummaltakin kaksikon jäseneltä yksi avain joka on molemmilla ja jota miltään muulta parilta ei ole vielä poistettu. Kun kukin rosvo kuluu neljään eri kaksikkoon, poistetaan kultakin neljä avainta ja jäljelle jää kuusi. Näin on varmistettu että mikään kaksikko ei saa kaikkia lukkoja auki.

Viidellä rosvolla on siis kullakin kuusi avainta eli kaikkiaan 30 avainta. Erilaisia lukkoja ja avaimia on 10 kpl joten kutakin avainta jää rosvoille 3 kpl. Kun alkuperäinen jako tehtiin tasan ja niin että kukin saa vain yhden kappaleen kutakin avainta, täytyy kutakin avainta olla yksi kappale kolmella eri rosvolla. Siksi millä tahansa rosvokolmikolla on nuo 10 avainta ja se saa oven auki.

Eli vastaus on: 10 lukkoa ja 6 avainta rosvoa kohti.

Kunnon rosvot eivät enää harrasta kellaripiiloja. Kunnon rosvot nauttivat veroparatiiseista ja niistä saatavista "pöytälaatikko" firmapalveluista.
Unohda ne kellaripiilot ja tule jo digitalisoidun maailman todellisuuteen jossa varallisuus vilahtaa veroparatiisin pankin turvaan sekunnin murto-osissa

PS. kellaripiiloa parempi piilo on vaikka oma tontti. Kyllä sinne "mullan alle" mahtuu piilopaikkoja. Seuraatko edes tv-uutisia lainkaan? Ja kunnon rosvo pitää saaliin kokonaan itsellä eikä jaa siitä osia muille. (joten tuo 20 %:n eli viidesosan osuus saaliista on todella liian vähän kunnon rosvolle)
Miksi jakaisit saaliin kun voit pitää koko saaliinkin, koska kaverisi ovat liian tyhmiä tajutakseen muuta kuin perinteisen kellaripiilon?

Tässä esimerkki avaimien jaosta:
0000111111
0111000111
1011011001
1101101010
1110110100
Mutta entäpä jos vaadittaisiinkin, että neljän viidestä rosvosta pitäisi olla paikalla?

Kolme samanlaista lukkoa, jokaisella rosvolla yksi lukkoon sopiva avain.
Eli tehtävässä olisi varmaankin ollut hyvä kertoa, että lukot ovat riippulukkoja, jotka voi jättää auki ilman avainta.

10 lukkoa, kullakin rosvolla 4 avainta, yhteensä 20. Komen kombinaatioita on 10 ja kun kutakin avainta on 2, saa neljän ryhmä varmasti kaikki auki.

Lukot ovat vain hidasteita ei esteitä. Jatkakaa vaan näitä lukkoleikkejänne, osaavat kunnon rosvot ovat jo menneet niistä lukituksista läpi.
Kunnon rosvo ei piilota ryöstövarojaan lukittuun kellariin vaan veroparatiisiin.

Koska lukot saa auki vain kun vähintään kolme rosvoa on paikalla niin mikään kahden rosvon porukka ei saa kaikkia lukkoja auki.Eli on aina vähintään yksi lukko jota kukin pari ei saa auki.Oletetaan että rosvot A ja B eivät saa auki tiettyä lukkoa L.Tällöin jokaisen muun rosvoista C,D ja E täytyy saada tuo L auki, muuten kolmen rosvon kopla (A,B,C),(A,B,D) tai (A,B,E) ei saa kaikkia lukkoja auki.Jokainen rosvopari siis ei saa auki tiettyä juuri heille ominaista lukkoa.On C(5,2) = 10 kahden rosvon paria joista kukin ei voi avata tiettyä juuri heille ominaista lukkoa. Lukkoja täytyy siis olla vähintään 10.

Jos R on nyt yksi rosvoista (siis A,B,C,D tai E) niin on C(4,2) = 6 kahden rosvon paria joissa R ei ole mukana ja kukin näistä pareista ei saa auki yhtä tiettyä lukkoa.Koska jokainen kolmen rosvon kopla saa auki kaikki lukot, R:llä täytyy olla avaimet jokaiseen näistä kuudesta luukosta.Jokaisella rosvolla tulee siis olla vähintään 6 avainta.

Riittääkö 6 avainta? Jos avaimia on kaikkiaan 10 niin kymmenelle rosvoparille voidan antaa 9 avainta siten että millään parilla eivät nämä avaimet ole samat sillä C(10,9) = 10.Jokaiselta parilta (R,S) puuttuu siis yksi tietty avain. Tämä avain on kuitenkin kaikilla muilla yhdeksällä parilla. Jos ei olisi jollain parilla niin tämän parin kumpikaan rosvo ei pystyisi täydentämään (R,S)-paria kolmikoksi joka saa kaikki lukot auki.

Merkitään parilta (R,S) puuttuvaa avainta K(R,S).Otetaan esimerkiksi pari (A,B).Tällöin K(A,B) on kaikilla muilla pareilla. Sen on silloin oltava myös jokaisella muulla rosvolla C,D ja E sillä jos se ei olisi esim. rosvolla C niin sitä ei olisi myöskään pareilla (A,C) ja (B,C) sillä K(A,B) puuttuu sekä A:lta että B:ltä. Sama pätee rosvoihin D ja E.

Näin ollen jokaisen parin (R,S) puuttuva avain on jokaisella muulla rosvolla kuin R tai S. Kolme rosvoa riittää aina avaamaan lukot jos niitä on 10, avaimia niinikään 10 ja jokaiselle rosvolle annetaan tietyllä tavalla 6 avainta.

Tämän voisi sanoa toisinkin. Eri rosvopareja on 10 ja avaimia 10. Olkoon f(i) se rosvopari jolta puuttuu avain i.Tämä on bijektio. Jokainen tällainen bijektio määrittelee mahdollisen avainten jaon rosvoille.

Annoinpa nyt vähän toisenlaisen todistuksen. En osallistu tällä mihinkään todistusten paremmuuskilpailuun.

Ohman