Den korte version: Niels Dalgaard og jeg starter nu en ny podcast, Robotter på loftet.
Den lidt længere version: Når man har puslet med noget lidt hemmeligt, så er det skønt endelig at kunne dele det med verden. Så kan man fx sige: Se vores fine logo!
Vi håber, at I har lyst til en podcast, hvor vi snakker science fiction-noveller.
This week the question is: Can You Beat the Heats?
There are 25 sprinters at a meet, and there is a well-defined order from fastest to slowest. That is, the fastest sprinter will always beat the second-fastest, who will in turn always beat the third-fastest, and so on. However, this order is not known to you in advance.
To reveal this order, you can choose any 10 sprinters at a time to run in a heat. For each heat, you only know the ordinal results, so which runner finishes first, second, third, and so on up to 10th. You do not know the specific finishing time for any runner, making it somewhat difficult to compare performances across heats.
Your goal is to determine with absolute certainty which of the 25 sprinters is fastest, which is second-fastest, and which is third-fastest. What is the fewest number of heats needed to guarantee you can identify these three sprinters?
And for extra credit:
At a different meet, suppose there are six sprinters that can race head-to-head. (In other words, there are only two sprinters per heat.) Again, they finish races in a consistent order that is not known to you in advance.
This time, your goal is to determine the entire order, from the fastest to the slowest and everywhere in between. What is the fewest number of head-to-head races needed to guarantee you can identify this ordering?
Highlight to reveal solution:
After a heat, I can eliminate the 7 slowest sprinters. I need to narrow the field to 3 sprinters. 25 – 3 = 22 = 3 * 7 and a bit. So I need 4 heats, just to find the top 3.
(Assume there is no faster way to do this, like choosing the sprinters for the 3rd heat in a clever way. I can’t think of such a clever procedure.)
Luckily that’s also enough to determine their order. Spend 3 heats eliminating 21 sprinters (always choosing sprinters that haven’t been eliminated yet), and there’s 4 left. The 4th heat will clearly show their internal order.
We need 4 heats.
And for extra credit:
With 2 sprinters, it’s easy. A and B race, we’re done.
With 3 sprinters, we need a little more. A and B race, turns out (WLOG) that A is the fastest. We want to check whether C fits in between them. So we race C against (WLOG) A. If C wins, we’re done. If not, we also need to race C against B. At most 3 races.
| Order | Race | Winner | Order |
| (1) A B | A | A B | |
| (1) A B | B | B A | |
| A B | (2) A C | A | A (B or C) |
| A B | (2) A C | C | C A B |
| B A | (2) B C | B | B (A or C) |
| B A | (2) B C | C | C B A |
| A (B or C) | (3) B C | B | A B C |
| A (B or C) | (3) B C | C | A C B |
| B (A or C) | (3) A C | A | B A C |
| B (A or C) | (3) A C | C | B C A |
(Going forward, I assume it’s possible to just add the nth sprinter to n-1 ordered sprinters, and that this is efficient. That I can’t do something clever like, I don’t know, shuffling 2 ordered groups into each other.)
With 4 sprinters, the complexity grows again. Assume we need 3 heats to order A, B and C. Turns out (WLOG) that the order is A B C. First we race B and D. If D wins, race A and D. If D wins again, it’s D A B C. If D loses, it’s A D B C. If on the other hand D loses to B, race D and C. If D wins, it’s A B D C. If D loses, it’s A B C D. 3 + 2 heats.
Notice D didn’t have to race everybody. Racing against B eliminates some options.
With 5 sprinters, there’s a little leap again. We use 5 races to obtain (WLOG) the order A B C D. Race E against (WLOG) B. Worst case, B loses and loses to C and will have to race D. 5 + 3 races.
With 6 sprinters, it’s more of the same. I want to add F to (WLOG) A B C D E, obtained after at most 8 races. Race against C, then against A or D, and worst case against B or E. 8 + 3 = 11 races.
Note: Binary Insertion Sort. There’s something going on with log2 here. I need 1 race to add a 2nd sprinter, 2 races to add a 3rd sprinter, 3 races to add a 5th sprinter. log2( x – 1) + 1 races to add the xth sprinter?
Ye olde website will continue to be available on http://ommadawn.dk.d.r101.wbsprt.com/ .
If this site (stuff.ommadawn.dk) should stop working, please use https://stufffromommadawn.wordpress.com/ instead.
Cradle of Empires, woohoo!
One of the mechanisms in this game is that some of the time the player is rewarded for completing a lot of levels in a row. This is shown by Fennec gradually having more boosters for you. And it looks like this:
An adorable and happy little fellow.
If everything should come tumbling down: Look for me at:
Quite suddenly this webpage might disappear for a while. Garbage with the domain registration and a migration has come up. Sigh.
Den her hjemmeside forsvinder muligvis i en periode. Alt muligt skrammel med registreringen af domænet og en ny struktur hos udbyderen og alt muligt.
Yes, I’m on a Cradle of Empires trip right now.
I’m sometimes confused about locations of stuff. Like, I’ll have a note, that the brewery is ready to be updated. But where is it? So, I made a map.
On this map, I’ve also noted the abbreviations I use.
| A | FAR | GU | POT | SPH |
| BA | FIE | H | PY | SPI |
| BR | FIS | MA | Q | TE |
| C | FO | MO | SE | TH |
| FAC | GA | POR | SH | TO |
In my notes.
Yes, I had some negative stuff to say about Cradle of Empires. But there’s also positive points. Like, would you look at these background. That usually aren’t on the screen very long.
This week the question is: Can You Win the Collaborative Card Game?
You and a friend each have a standard deck with 52 cards. You thoroughly shuffle your deck, while your friend thoroughly shuffles theirs. Then, you both draw cards one at a time. If the first card you draw is the same as the first card your friend draws, you lose! Otherwise, you draw again. If the next card you draw is the same as the next card your friend draws, you lose! Otherwise … and so on.
If the two of you can make it through your entire decks without ever drawing the same card at the same time, you both win. Otherwise, you both lose.
What is the probability that you and your friend will win this collaborative game?
Highlight to reveal solution:
I wrote a program to simulate the situation, at least with a deck with 2-9 cards. I reduce to a situation, where deck 1 is simply n numbered cards, going from 1 to n. Then I go through all the permutations of deck 2. There seems to be convergence. I guess the answer is 36.79%. I have no idea why.
Anmeldelse af “The Tinker and the Timestream” (gratis), af Carolyn Ives Gilman.
Skitse: Rustem (et arabisk navn?) bor i en landsby, som er del af en mislykket koloni. De skulle slet ikke have været på den her planet, og de skulle ikke have boet under en ustabil sol. Situationen er deprimerende, og nogle af beboerne har, host, fået fornyet interesse for overtro. Og så en aften ser Rustem, der prøver at holde liv i videnskab, et stærkt lys på himlen.
Er det science fiction? Jeps.
Temaer: Sjov med tid! Og med besøgende, der påstår, de har et lille fartøj, der kan navigere på tidsstrømmene.
Rustem har det godt med orden, så det er hårdt at vænne sig til et stykke tid at have noget andet. Og at vænne sig til en Spørgejørgine.
Er det godt? Ja. Ja, det er det egentlig. 👽👽👽
Stuff from ommadawn.dk (Lise Andreasen) 