Binär kodning
Problem 1. Du (en ond mästare) har 1000 vinflaskor, varav en innehåller ett långsamtverkande gift. Den som får i sig ens en liten klunk av det kommer obönhörligen dö inom en månad. Du vill ta reda på vilken flaska det är som innehåller giftet, och till din hjälp har du en mängd tjänare som är godtrogna nog att dricka vadhelst du serverar dem. Hur många tjänare behöver du servera vin till för att kunna hitta flaskan inom en månad, dvs på ett försök?
Svar: Det är lätt att klara sig med 1000 stycken (eller rent av 999) - låt alla dricka ur var sin flaska, och se vilken som dör. Dock är det inte optimalt, vilket man inser om man tänker på hur mycket information man får ut från en viss tjänare - om han dör så får man direkt veta vilken flaska som är förgiftad, och dessutom informationen att alla andra tjänarna överlevde. Det vore mer optimalt om VARJE tjänares överlevnad eller död påverkade resultatet.
Det går snabbt att inse att en grupp på n tjänare kan överleva/dö på 2^n olika sätt. Då 2^9 = 512 < 1000 < 1024 = 2^10 får vi att 9 tjänare är absolut för lite, men att 10 tjänare kanske går. Det gäller bara att komma på ett system så att varje vinflaskas förgiftning motsvarar (exakt) ett sätt för tjänarna att överleva/dö på. Det lättaste sättet är att använda det binära talsystemet:
Flaska 0 = 0000000000: ingen tjänare får del av detta vin
Flaska 1 = 0000000001: tjänare #10 får del av detta vin
Flaska 2 = 0000000010: tjänare #9 får del av detta vin
...
Flaska 375 = 0101110111: tjänare #2, #4, #5, #6, #8, #9, #10 får del av detta vin
...
Flaska 1000 = 1111101000: tjänare #1, #2, #3, #4, #5, #7 får del av detta vin
Om t.ex. tjänare #2, #4, #5, #7 och #9 dör så vet vi att den förgiftade flaskan har nummer 0101101010 = 362.
Problem 2. I ett rum finns 1000 strömbrytare. En trappa upp finns en lampa som är kopplad till en av dessa strömbrytare. Hur många gånger måste du minst gå upp för trappan för att ta reda på vilken strömbrytare?
Svar: Det här är i princip samma problem som det förra, fast tjänarna är utbytta mot motionspass i trappan. Det krävs alltså 10 sådana. (I första steget kan man till exempel slå på 1,3,5,7,...; sedan 2,3,6,7,10,11,... ; sedan 4,5,6,7,12,13,14,15,20,21,22,23,...)
Om man inte vet vad som är på och av på alla brytare krävs det en tur till, eftersom antalet möjligheter fördubblas ("Lampan är kopplad till brytare #163" blir till "Lampan är kopplad till brytare #163 och ner betyder på" och "Lampan är kopplad till brytare #163 och ner betyder av").
Har man extra mycket tid kan man ta till värmetricket, så att lampan kan vara i tre olika tillstånd: av och kall, av och varm, samt på. Då får man räkna i bas tre, och för 1000 brytare (med känd position) krävs 7 promenader då 3^6 = 729 < 1000 < 2187 = 3^7.
Problem 3. I elcentralen till en villa finns 19 jordfelsbrytare (avancerade proppar). Hur många gånger måste du gå igenom huset och testa varje eluttag och lampa för att ta reda på vart allt är kopplat?
Svar: 5 gånger.
1. Lampor ÖV inkl. balkong och trappa
2. Lampor BV: arbetsrum, sovrum, kök, matsal, balkong; köksfläkt, uttag vid fläkt.
3. Lampor BV: hall, ute, vardagsrum; uttag hall & vardagsrum vid innerväggen; badrum BV
4. Uttag allrum; uttag hall & vardagsrum vid ytterväggen; badrum & bastu KV
5. Lampor pannrum; mikro, uttag vid mikro
6. Diskmaskin
7. Uttag A tvättstuga
8. Spishäll
9. Ugn
10-15. Inget
16. Tvättmaskin
17. Garage inkl. utsidor; tvättstuga förutom tvättmaskin och uttag A; gillestuga förutom lampor; kyl, frys, uttag vid frys
18. Uttag arbetsrum, sovrum BV, 2 sovrum ÖV, kök i södra hörnet, vardagsrum i norra hörnet; lampor gillestuga; hobbyrum; matkällare; trappa KV
19. Inget
Det konstiga är att brytare 17 brukade vara 5 olika proppar innan vi installerade jordfelsbrytare. Då skulle vi kunna köra torkskåp, dammsugare KV, vattenkokare och motorvärmare samtidigt utan risk att slå ut kyl/frys och källar-TV:n. Nu kan man bara göra en sak åt gången.
Svar: Det är lätt att klara sig med 1000 stycken (eller rent av 999) - låt alla dricka ur var sin flaska, och se vilken som dör. Dock är det inte optimalt, vilket man inser om man tänker på hur mycket information man får ut från en viss tjänare - om han dör så får man direkt veta vilken flaska som är förgiftad, och dessutom informationen att alla andra tjänarna överlevde. Det vore mer optimalt om VARJE tjänares överlevnad eller död påverkade resultatet.
Det går snabbt att inse att en grupp på n tjänare kan överleva/dö på 2^n olika sätt. Då 2^9 = 512 < 1000 < 1024 = 2^10 får vi att 9 tjänare är absolut för lite, men att 10 tjänare kanske går. Det gäller bara att komma på ett system så att varje vinflaskas förgiftning motsvarar (exakt) ett sätt för tjänarna att överleva/dö på. Det lättaste sättet är att använda det binära talsystemet:
Flaska 0 = 0000000000: ingen tjänare får del av detta vin
Flaska 1 = 0000000001: tjänare #10 får del av detta vin
Flaska 2 = 0000000010: tjänare #9 får del av detta vin
...
Flaska 375 = 0101110111: tjänare #2, #4, #5, #6, #8, #9, #10 får del av detta vin
...
Flaska 1000 = 1111101000: tjänare #1, #2, #3, #4, #5, #7 får del av detta vin
Om t.ex. tjänare #2, #4, #5, #7 och #9 dör så vet vi att den förgiftade flaskan har nummer 0101101010 = 362.
Problem 2. I ett rum finns 1000 strömbrytare. En trappa upp finns en lampa som är kopplad till en av dessa strömbrytare. Hur många gånger måste du minst gå upp för trappan för att ta reda på vilken strömbrytare?
Svar: Det här är i princip samma problem som det förra, fast tjänarna är utbytta mot motionspass i trappan. Det krävs alltså 10 sådana. (I första steget kan man till exempel slå på 1,3,5,7,...; sedan 2,3,6,7,10,11,... ; sedan 4,5,6,7,12,13,14,15,20,21,22,23,...)
Om man inte vet vad som är på och av på alla brytare krävs det en tur till, eftersom antalet möjligheter fördubblas ("Lampan är kopplad till brytare #163" blir till "Lampan är kopplad till brytare #163 och ner betyder på" och "Lampan är kopplad till brytare #163 och ner betyder av").
Har man extra mycket tid kan man ta till värmetricket, så att lampan kan vara i tre olika tillstånd: av och kall, av och varm, samt på. Då får man räkna i bas tre, och för 1000 brytare (med känd position) krävs 7 promenader då 3^6 = 729 < 1000 < 2187 = 3^7.
Problem 3. I elcentralen till en villa finns 19 jordfelsbrytare (avancerade proppar). Hur många gånger måste du gå igenom huset och testa varje eluttag och lampa för att ta reda på vart allt är kopplat?
Svar: 5 gånger.
1. Lampor ÖV inkl. balkong och trappa
2. Lampor BV: arbetsrum, sovrum, kök, matsal, balkong; köksfläkt, uttag vid fläkt.
3. Lampor BV: hall, ute, vardagsrum; uttag hall & vardagsrum vid innerväggen; badrum BV
4. Uttag allrum; uttag hall & vardagsrum vid ytterväggen; badrum & bastu KV
5. Lampor pannrum; mikro, uttag vid mikro
6. Diskmaskin
7. Uttag A tvättstuga
8. Spishäll
9. Ugn
10-15. Inget
16. Tvättmaskin
17. Garage inkl. utsidor; tvättstuga förutom tvättmaskin och uttag A; gillestuga förutom lampor; kyl, frys, uttag vid frys
18. Uttag arbetsrum, sovrum BV, 2 sovrum ÖV, kök i södra hörnet, vardagsrum i norra hörnet; lampor gillestuga; hobbyrum; matkällare; trappa KV
19. Inget
Det konstiga är att brytare 17 brukade vara 5 olika proppar innan vi installerade jordfelsbrytare. Då skulle vi kunna köra torkskåp, dammsugare KV, vattenkokare och motorvärmare samtidigt utan risk att slå ut kyl/frys och källar-TV:n. Nu kan man bara göra en sak åt gången.
Kommentarer