This week the #puzzle is: Can You Play Hide-and-Seek? #minimum #maximum #minmax #coding #probabilities #InfiniteSum #integral
I (Nis) am playing hide-and-seek with my nephew. I start at point O, whereas my nephew can hide at point A, B or C. I can walk from O to A in 2 minutes, from O to B in 3 minutes, from O to C in 4 minutes, and from B to C in 5 minutes. To get from A to B or from A to C, I must pass through O.
My goal is to minimize the time it takes to find him, no matter how clever his strategy might be. What is this optimal time?
And for extra credit:
My nephew can no longer hide at C, and is instead limited to A and B. But this time, he has a teleporter that can instantaneously transport him from A to B or from B to A. He can use the teleporter as many times as he wants. However, he can’t react to my approach, and must instead plan out his transport schedule ahead of time. That said, he does know the precise time when the game starts.
My goal is to minimize the average time it takes to find him, no matter how clever his strategy might be. What is this optimal time?
So, I’m looking for a strategy, where the maximum time is minimized. The maximum time is the time required to look in both A, B and C.
A strategy should look in both A, B and C. It can described by the order in which Nis visits these places. Nephew’s strategy can be described by where he is hiding. Let’s look at all the strategies and all the related times. (I did these by hand and confirmed them with a program.) Nis’s strategies going down, Nephew’s strategies going across:
A
B
C
Max
ABC
2
7
12
12
ACB
2
13
8
13
BAC
8
3
14
14
BCA
14
3
8
14
CAB
10
15
4
15
CBA
14
9
4
14
Example of calculation: ACB is actually the path OAOCB, and the time required is 2 + 2 + 4 + 5 = 13.
The min-max occurs with the strategy ABC, and the time is 12 minutes.
Method 1: I modify my program to also look at teleporter strategies. A strategy for Nis can still be described by the order in which he looks in different places, but he might have to look in more than 2 places, and he has the option to stand still in 1 place for a while. For Nephew there’s a sample rate involved. To keep things simple, I say that Nis (when not on the move) looks once every minute. The strategy BBA for Nis would be: go to B and look immediately, wait 1 minute and then look again, and finally go to A. A strategy for Nephew has to describe where he is when Nis is looking. BBA would describe being at B after 1 and 2 minutes and then at A after 3 minutes. Both sets of strategies will stretch to infinity, as the worst case is that Nis never finds Nephew. But I put in a limit in the program, where I simply say, if Nephew hasn’t been found by this time, assume the time will be finite, but large. I also keep track of how many times I invoke this large time.
My program produces something like this:
Winner: AAAAAAAAAAA, time 3.10449, 4 cases out of 4096 of not being found Winner: AAAAAAAAAAB, time 3.10449, 4 cases out of 4096 of not being found
And I go: oooh.
Method 2: Assume AAA… is the best strategy.
1: Can I argue, that this might be the case?
Let’s look at 4 simple classes of strategies for Nis, beginning with AA, AB, BA and BB.
AA uses 2 minutes to get to A and then stays there for 1 minute.
AB uses 2 minutes to get to A and then uses 5 minutes to go to B.
BA uses 3 minutes to get to B and then uses 5 minutes to go to A.
BB uses 3 minutes to get to B and then stays there for 1 minute.
And how are these doing against Nephew’s strategies? * is used as a wild card.
AA finds Nephew with the strategies *A* and **A*.
AB finds Nephew with the strategies *A* and ******B*.
BA finds Nephew with the strategies **B* and ********A*.
BB finds Nephew with the strategies ***B* and ****B*.
AB and BA are horrible. It takes 2-3 minutes to look in 1 place, and then 5 more minutes to look in the next. All that time wasted. AA and BB seems better. Further AA looks better than BB, because it starts looking earlier. So, case argued. Go to A and stay put. Sooner or later Nephew will show up.
2: What is the average time of the strategy AAA…?
If I’m still working with a sample rate, Δ, this goes into my calculation.
After 2 minutes Nis looks for Nephew at A. Half his strategies has him there, and Nis finds him.
After 3 minutes Nis looks for Nephew at A again. Half of his remaining strategies has him there, and Nis finds him.
This represents this average of times:
Or to use my variable Δ:
So far we have the result, that the average time is 2 minutes or more. Makes sense.
If I simply let Δ = 0, the whole average time will be 2 minutes.
HOWEVER. Nis is not playing against all strategies. Nephew knows about this strategy and might simply decide to go to B and stay there. In which case E(t) = ∞. Not good.
Method 1 again: I look at some of the other candidates for strategies. Hm.
Method 3: Assume a best strategy. A best strategy has to include some randomness, otherwise Nephew could just always be the other place. It also has to discard the idea of a sample rate, because Nephew could fight that having a higher teleporter rate. “You didn’t find me at A, because I was at B? Well, now I will stay at B for 5 minutes, knowing you can’t catch me there. Well, 4 minutes, just to make sure.”
Those 5 minutes have to figure into Nis’ strategy.
Randomness. Begin by looking at A or B, but randomly. It can’t pay to look at A early, even though it’s possible, Nephew could simply decide to be at B at this time. So look at either A or B after 3 minutes. (The latter is the strategy “B”. The former is “AA”. Or maybe “OA”, that is, staying at O for 1 minute before going to A. Or maybe simply “-A”, signifying 1 minute of random walking + 2 minutes of walking from O to A.) Choose between “B” and “-A” by the flip of a coin. Both looking at A and looking at B are now equally probable. Nephew doesn’t have any advantage of choosing one over the other. I assume Nephew will also flip a coin to choose either A or B. So after 3 minutes, half of the time Nephew will be found.
The next step is to be at A or B with equal probability some time later. It takes 5 minutes to switch places, so that has to be the next time, 3+5 = 8 minutes. The 4 resulting strategies could be “-A—-A”, “-AB”, “B—-A” and “B—-B”. (Walking between A and B for 5 minutes. Or walking between A and A for 5 minutes.) Again, half of the time Nephew will now be found.
The average time looks like this, upcycling the formula from above.
Overvældende godt felt! Det er svært. Kaijuen skulle måske i virkeligheden kun have 2,5/3. Men så er der stadig 3 kandidater tilbage. Murderbot er jo dejlig. Vegetaren er også stadig charmerende. Så måske er pigen på tredjepladsen. Decisions, decisions! Det bliver Murderbot som nr. 1.
Skitse: Fortælleren har egentlig et solidt liv. Hun blev gift med Charlie, og sammen fik de noget fornuftigt ud af en kedelig grund med en ramponeret lade. Det blev et hjem. De elskede hinanden. Så hvorfor har hun bundet Charlie til sengen, mens han råber en andens navn, og hvorfor sidder hun selv ude på verandaen med et haglgevær?
Er det science fiction? Nix. Fantasy/horror.
Temaer: Det kom snigende ind, at da den andens navn blev afsløret, så kendte jeg jo godt noget af den her historie. Omend det er nyt, at der er overnaturlige kræfter involveret.
Der er en diskussion af begrebet ejerskab. At et ægtepar kan eje et hjem. At en kvinde kan eje sin mand?
Citat: “He bellowed for her out of the belly of the house.”
Er det godt? Ja. Men slutningen virkede brat på mig. ##-
Skitse: Et show kan indeholde alle mulige små numre: den trænede hund, akrobater. Både fortælleren og “Millay”, tidligere Miller, er tryllekunstnere. Og kvinder. Den ene klæder sig ud som mand, den anden optræder fjollet. Fordi kvinder kan jo ikke lave seriøst, dygtigt tryl.
Er det science fiction? Nej. Fantasy?
Temaer: Tryl. Kvinder. Sexisme.
Er det godt? Ja da. Men jeg gættede godt nok næsten slutningen for tidligt. ##-
Skitse: En stinkerig kvinde leder et forretningsimperie. Desuden “lever hun evigt”, i den forstand, at den næste leder skal være hendes egen klon. Opdraget på samme måde som stifteren af imperiet, sådan som man gør i hver generation. Fortælleren skal være gravid med klonen og siden opdrage barnet. Det er ikke nogen økonomisk fest, men det er meget mere stabilt end alternativet, hvor en gåtur om sommeren indebærer brændemærker fra fortovet, når man besvimer i varmen. Desværre er det kun blevet til en stribe aborter indtil nu, så er ny pige er ved at blive installeret, der kan overtage jobbet.
Er det science fiction? Ja.
Temaer: Der er en del af plottet, der kredser om en teknologi, hvor konstruerede kroppe kan modtage en uploadet person. Det er fx genialt at blive en superstærk vagt, når man ellers ikke rigtig kunne få et job i sin kedelige, normale krop.
Fortælleren er en transkvinde, og det spiller på flere måder en stor rolle i historien.
Skitse: Det gode rumskib Perihelion er i gang med en mission, som Iris leder. De skal besøge en rumstation. Der lige er blevet erobret af en fjendtlig gruppe. Øv.
Er det science fiction? Jepper.
Temaer: Langnovellen er del af Murderbot-serien, omend det her er en usædvanlig del af serien, dels fordi den foregår tidligere i kronologien end den foregående historie, dels fordi Murderbot ikke selv er med. Men bare rolig. Perihelion er på enhver måde Murderbots gode ven, inklusive alle de verbale stikpiller.
Historien kommer til at dreje sig om Peri, der tydeligt er påvirket af at have mødt Murderbot. Mødt? Påvirket? Hvad betyder de ord, når begge parter er konstruerede personer, der ikke opfører sig 100 % som mennesker, og Peri er et rumskib?
Iris og hendes gruppe kommer fra et ikke-kapitalistisk samfund, så vi ser hele tiden deres reaktioner på penge & co.
Er det godt? Åh ja. Iris er rigtig rar at være sammen med og håndterer Peris krise på en god måde. ###
This week the #puzzle is: Can You Drink the “Random-ade”? #MonteCarlo #coding #probabilities
I’m preparing a mixture of “random-ade” using a large, empty pitcher and two 12-ounce glasses.
First, I fill one glass with some amount of lemon juice chosen randomly and uniformly between 0 and 12 ounces. I fill the other glass with some amount of water, also chosen randomly and uniformly between 0 and 12 ounces. Next, I pour an equal amount from each glass into the pitcher until one of the glasses is empty.
At this point, I refill that empty glass with yet another random amount of the same liquid it previously contained. Once again, I pour an equal amount from each glass into the pitcher until one of the glasses is empty.
On average, how much random-ade can I expect to prepare? (Note that all three random amounts in this problem are chosen independently of each other.)
And for extra credit:
Once again I’m preparing random-ade, but this time I have three 12-ounce glasses.
I fill the first glass with a random amount of lemon juice, the second glass with a random amount of lime juice, and the third glass with a random amount of water. As before, each amount is chosen uniformly between 0 and 12 ounces, and all amounts are independent. Next, I pour an equal amount from each glass into the pitcher until one of the glasses is empty.
At this point, I refill that empty glass with yet another random amount of the same liquid it previously contained. Once again, I pour an equal amount from each glass into the pitcher until one of the glasses is empty.
Then I refill that now-empty glass with yet another random amount of the same liquid it previously contained. Again, I pour an equal amount from each glass into the pitcher until one of the glasses is empty.
On average, how much random-ade can I expect to prepare?
Skitse: Galaksen fungerer sådan, at de gamle, vise rumvæsener patruljerer rundt blandt planeterne. Når en planet viser tegn på at kunne have intelligent liv, så smider de et frø ned, der er klar til at vokse op og gøre noget ved sagerne, hvis intelligenserne opfører sig dumt. Således fik Jorden sådan et frø for 200.000 år siden. Efter WW2 er der radioaktivitet i luften, så frøet vågner op. Bliver til en kaiju. Tramper rundt. Bliver slået ned. Tror man. Monsteret i Stillehavet bliver flittigt diskuteret i både Moskva og Washington.
Er det science fiction? Ja da. Rumvæsener og alternate history, mums.
Temaer: Godzilla! Kaiju! Hvad du nu har lyst til at sige. Og jeg tror, der er guf her, hvis man har set filmene. Kaiju har lært princippet, at hvis man tramper rundt længe nok, så vil planeten opgive vold. Men sådan er mennesker jo ikke indrettet, næ nej.
En god del humor. Politikere er jo sjove? Og jeg klukkede da lidt, da Jacques Cousteau blev meldt savnet. Og da Kennedy lovede, at der indenfor et årti ville blive bygget en Kaiju-overvågende rumstation.
Er det godt? Jeg var bange for, at det hele skulle drukne i kommunist-klicheer, men tog heldigvis fejl. Det er sjovt. Det læner sig i hvert fald til dels opad noget historie og kultur, jeg kender. Der er en god slutning. ###
. 
Stuff from ommadawn.dk (Lise Andreasen) 