I hope you had a chance to play the clock solitaire game that was listed yesterday. When we were kids we laid out six cards face down in one horizontal row, then six cards in a row below that one, and a single card to the right of the two rows. The top row was labeled (in our head) Ace through Six; the bottom row was labeled Seven through King, but we skipped over the Jack. The card on the right was the Jack. We then dealt out all the cards evenly into the thirteen stacks, so each stack had four cards in it. You start the game by picking up the top card in the Jack pile. Whatever card it was, you slid it face up under that stack. So if you picked up a Five, you slid that Five under the Five stack and then picked up the top card in that stack. If that card was a Ten, you slid it face up under the Ten pile and took the top card. You kept doing that until you ran out of cards to turn over. Your goal was to get all the cards in the stacks turned over before the last Jack came up. When the last Jack came up, there were no more cards in the Jack pile to work with (since you started with that pile) so the game was over. There is roughly a 1% chance of winning so it was a huge victory when you did win.
That is similar to the strategy for the 100 Prisoners Problem. Each contestant walks to the box that corresponds to their number. Contestant 1 walks to the first box, opens it, then moves to the box whose number is on the dollar bill in the first box. So if the first box has a 67 on the dollar bill, you would go to Box 67 next. If that box has a dollar bill numbered 43 in it, you would then go to Box 43. You keep repeating this until the box you open has your number - in this case number 1. So now you know which box has dollar bill number 1 in it and you can leave. Contestant 2 walks to Box 2 and checks the number. Then he moves to the Box with that number and so on until he either finds the box with 2 in it or hits his 50 box limit. Contestant 3 starts with Box 3 and so forth.
Let's look at a much simpler version that has only 8 boxes and 8 contestants. The box numbers and dollar bill numbers are listed below. Assume that the limit on boxes you are allowed to open is 4 = half of 8, just like 50 = half of 100.
Box number 1 2 3 4 5 6 7 8
Number on dollar bill 4 7 5 2 6 3 1 8
inside
Where did those numbers come from? I made them up just as the designer of the puzzle would do when they put the dollar bills in the boxes.
Contestant 1 finds a 4 in Box 1 so they go to Box 4, then to Box 2, then to Box 7 and there they find the dollar bill numbered 1 and they leave. They opened 4 boxes, so the game is still going on. Contestant 2 starts at Box 2, then Box 7, Box 1, and finishes at Box 4 (where he finds his number 2 dollar bill). Contestant 3 starts at Box 3, then to Box 5, then Box 6 and they are finished. What we have are cycles of numbers:
(1, 4, 2, 7) is a cycle. If you start at one of these numbers, like 2, you will cycle through the other numbers in the group: 2 goes to 7 then to 1, then to 4. (3, 5, 6) is also a cycle and (8) is a cycle by itself. Because each cycle is 4 or smaller, each contestant will find their number successfully and everyone gets the prize money.
Here's another allotment of dollar bills.
Box number 1 2 3 4 5 6 7 8
Number on dollar bill 2 3 4 5 6 1 8 7
inside
Here the cycles are (1, 2, 3, 4, 5, 6) and (7, 8) and the contestants would lose because the first cycle is longer than 4 numbers.
With the 100 box problem, the contestants would win if the longest cycle of numbers is 50 numbers or less. There can't be more than one of those because there are only 100 numbers to divvy up into cycles. So there could be a 20 number cycle, a 30 number cycle, and a 50 number cycle and that would use up all the numbers (and you would win). The probability calculations (found here, if you would like to follow along) tell us that the longest cycle of numbers is 50 or less about 31% of the time. That is a huge jump from the random strategy probability of winning which was 0.0000000000000000000000000000008.
Thursday, December 11, 2014
Wednesday, December 10, 2014
The 100 Prisoners Problem and a New Card Game
Today's math lesson is about probability, one of my favorite topics. The problem we are looking at is couched in terms of executing prisoners, so we are going to look at it from a less violent point of view. I should point out that this (roughly 10 year old problem) is not an easy problem to solve and I am not giving it to you to see how good at math you are. I thought the solution was very interesting and was reminded of it when I was killing time playing solitaire the other day. So you are going to see some interesting math and learn a new card game in the process.
Suppose 100 people have been selected at random, lined up, and given a number based on their spot in line. First person in line is number 1, second is number 2 and so on until the last person is given number 100. The first person is sent into a room which has 100 boxes in a row, each containing a dollar bill numbered from 1 to 100 also. The person's job is to find the box with the dollar bill that matches their number. So person number 1 will keep opening boxes until they find the dollar bill that has the number 1 on it. Here's the catch. The person is only allowed to open 50 boxes. If, after 50 boxes they have not found their dollar bill, the game is over and everybody is sent away. If they find their dollar bill, they leave it in the box, exit the room out a back door, and person 2 is allowed into the room. Person 2 is now charged with opening up to 50 boxes until they find the dollar bill labeled number 2. And so on. If at any time a person fails to find their dollar bill, the game is over and everybody goes home. If everybody finds their dollar bill, then everybody gets a prize of $1000. So, everybody wins or nobody wins. A significant part of the rules is that although people can speak to each other before they enter the room, there is no communication of any kind between people who have been in the room and those still waiting. That includes doing any writing on the boxes, rearranging the boxes in any way, leaving messages on the wall, etc. Every person entering a room must have the same information about the room that everyone else had, namely that there are 100 boxes with numbered dollar bills. (Remember each person who finds their dollar bill leaves it in the box looking just as it did before.)
Now if person 1 enters the room and starts picking boxes at random, there is a 50% probability that they will find their dollar bill. Person 2 also has a 50% probability of finding their dollar bill. The probability of the first two people then finding their dollar bills is 25% - .5 times .5 is .25. For three people, it is (.5) to the third power. And the probability of everyone being successful and therefore everyone winning the prize is (.5)100 ≈ 0.0000000000000000000000000000008 which is pretty small. In fact there is a clever non-random way to choose the boxes that raises that probability of winning the prize to about 31%. So I will give you some time to think about it (and time for me to write up the math) and come back tomorrow and post the solution here. If you would like a hint and, more importantly, a time-wasting card game to play when you are bored, look at the directions for "clock solitaire" listed here. This version isn't set up the way we played it as kids, but it is the same game. Play a few rounds and see if it leads you to a strategy for the 100 boxes game.
Suppose 100 people have been selected at random, lined up, and given a number based on their spot in line. First person in line is number 1, second is number 2 and so on until the last person is given number 100. The first person is sent into a room which has 100 boxes in a row, each containing a dollar bill numbered from 1 to 100 also. The person's job is to find the box with the dollar bill that matches their number. So person number 1 will keep opening boxes until they find the dollar bill that has the number 1 on it. Here's the catch. The person is only allowed to open 50 boxes. If, after 50 boxes they have not found their dollar bill, the game is over and everybody is sent away. If they find their dollar bill, they leave it in the box, exit the room out a back door, and person 2 is allowed into the room. Person 2 is now charged with opening up to 50 boxes until they find the dollar bill labeled number 2. And so on. If at any time a person fails to find their dollar bill, the game is over and everybody goes home. If everybody finds their dollar bill, then everybody gets a prize of $1000. So, everybody wins or nobody wins. A significant part of the rules is that although people can speak to each other before they enter the room, there is no communication of any kind between people who have been in the room and those still waiting. That includes doing any writing on the boxes, rearranging the boxes in any way, leaving messages on the wall, etc. Every person entering a room must have the same information about the room that everyone else had, namely that there are 100 boxes with numbered dollar bills. (Remember each person who finds their dollar bill leaves it in the box looking just as it did before.)
Now if person 1 enters the room and starts picking boxes at random, there is a 50% probability that they will find their dollar bill. Person 2 also has a 50% probability of finding their dollar bill. The probability of the first two people then finding their dollar bills is 25% - .5 times .5 is .25. For three people, it is (.5) to the third power. And the probability of everyone being successful and therefore everyone winning the prize is (.5)100 ≈ 0.0000000000000000000000000000008 which is pretty small. In fact there is a clever non-random way to choose the boxes that raises that probability of winning the prize to about 31%. So I will give you some time to think about it (and time for me to write up the math) and come back tomorrow and post the solution here. If you would like a hint and, more importantly, a time-wasting card game to play when you are bored, look at the directions for "clock solitaire" listed here. This version isn't set up the way we played it as kids, but it is the same game. Play a few rounds and see if it leads you to a strategy for the 100 boxes game.
Monday, December 8, 2014
A Movie Recommendation, Eventually
The movie / TV distribution business has been pretty chaotic over the last few years. Network TV has been losing market share pretty steadily, in spite of their commitment to copying whatever the hot new show was last year rather than trying to make something original. Cable has picked up the slack and seems to have the new hit shows, but they tend to be a little dark to sit down with the family and watch on a Sunday night. People tell me Game of Thrones, Dexter, House of Cards, Homeland, and Orange is the New Black are all great shows, but I haven't gotten into them. I miss Pushing Daisies and Life and Farscape. On the movie side, Netflix was the anti-Blockbuster. Get dvds in the mail, keep them however long you wanted, and lots of choices. Then came HULU and now there's HBO online and there are lots of choices for how to receive your movie. We still have Netflix, getting one dvd at a time, watching it almost immediately, and sending it back right away so that we are seeing a couple of movies a week this way. We also have lots of Netflix movies that can be streamed over the computer that we can watch on the big TV with the Apple TV box. We went to see the new Hunger Games 3A movie this week at the theater and realized we had forgotten most of the previous movie. So when we got home, we dialed up Hunger Games 2 on Netflix Streaming and watched it from the couch.
I like Netflix because we have seen a number of quirky movies over the years that we wouldn't have paid to see at the theater and many of them have been very good. Our most recent watching was a movie that I would recommend to my family because I know they have some of the same sensibilities we have. In particular, I know that music is very important to them. We have top ten lists for movies and for books on our Marshmallow Fight website, but when we looked at top songs, we knew it would take at least 25 to get all the songs onto the list that we wanted. So each person there has a top 25 list of songs, which, in the case of Dave and me, expanded to top 30 because we couldn't make the final 5 cuts. They are all great songs, but they aren't all there because they are great songs. Many of them are there because they are tightly connected to important moments in our lives. Psychologists tell us that smell is the sense most strongly tied to memory. Strong smells can trigger our memory of events long gone from our conscious mind. But I think music is equally powerful. And it's not just events. When I hear some Association songs, I am taken back to my Freshman year in college some 45 years ago. My roommate was a junior who loved the Association and had a stereo. You needed a record player back then as there were no ipods or smartphones and itunes wasn't even a ka-ching in Steven Jobs' eyes yet. You went to the record store if you wanted to buy a new album. There were people there who liked to talk about music. You might have a conversation with someone standing right next to you. OK, I've gotten off track here and started shouting at the kids to get off my lawn. Sorry about that. Anyway "Along Comes Mary" just sends me off thinking about late night talk sessions in the dorm, skateboarding along the Red Cedar River at two in the morning, and many other memories of my first year away from home and family.
There is a scene in the movie I am recommending where a record producer explains to a songwriter what a splitter does. You plug it (nowadays) into your phone or ipod, then the music is split into two sets of headphones. The producer, played by Mark Ruffalo in a wonderful turn as a jaded, declining middle aged man recovering from a meltdown in his life, relates the story of wandering around New York with his girlfriend many years ago, listening to each other's playlists. And that is a scene that I can easily see people I know recreating. Especially people who believe their playlist is a window into their heart and their soul.
The movie is called "Begin Again" and stars Keira Knightley and Mark Ruffalo, although the supporting cast is excellent as well. Ann and I both really liked it. The vocals in the movie are mostly done by Keira Knightley, Adam Levine (the front man for Maroon 5), and CeeLo Green (from the Voice) and, yes, I already downloaded the soundtrack to itunes. But the only one here to talk to during the download was Whimzy, so maybe I'll still go out to the record store for old times sake.
I like Netflix because we have seen a number of quirky movies over the years that we wouldn't have paid to see at the theater and many of them have been very good. Our most recent watching was a movie that I would recommend to my family because I know they have some of the same sensibilities we have. In particular, I know that music is very important to them. We have top ten lists for movies and for books on our Marshmallow Fight website, but when we looked at top songs, we knew it would take at least 25 to get all the songs onto the list that we wanted. So each person there has a top 25 list of songs, which, in the case of Dave and me, expanded to top 30 because we couldn't make the final 5 cuts. They are all great songs, but they aren't all there because they are great songs. Many of them are there because they are tightly connected to important moments in our lives. Psychologists tell us that smell is the sense most strongly tied to memory. Strong smells can trigger our memory of events long gone from our conscious mind. But I think music is equally powerful. And it's not just events. When I hear some Association songs, I am taken back to my Freshman year in college some 45 years ago. My roommate was a junior who loved the Association and had a stereo. You needed a record player back then as there were no ipods or smartphones and itunes wasn't even a ka-ching in Steven Jobs' eyes yet. You went to the record store if you wanted to buy a new album. There were people there who liked to talk about music. You might have a conversation with someone standing right next to you. OK, I've gotten off track here and started shouting at the kids to get off my lawn. Sorry about that. Anyway "Along Comes Mary" just sends me off thinking about late night talk sessions in the dorm, skateboarding along the Red Cedar River at two in the morning, and many other memories of my first year away from home and family.
There is a scene in the movie I am recommending where a record producer explains to a songwriter what a splitter does. You plug it (nowadays) into your phone or ipod, then the music is split into two sets of headphones. The producer, played by Mark Ruffalo in a wonderful turn as a jaded, declining middle aged man recovering from a meltdown in his life, relates the story of wandering around New York with his girlfriend many years ago, listening to each other's playlists. And that is a scene that I can easily see people I know recreating. Especially people who believe their playlist is a window into their heart and their soul.
The movie is called "Begin Again" and stars Keira Knightley and Mark Ruffalo, although the supporting cast is excellent as well. Ann and I both really liked it. The vocals in the movie are mostly done by Keira Knightley, Adam Levine (the front man for Maroon 5), and CeeLo Green (from the Voice) and, yes, I already downloaded the soundtrack to itunes. But the only one here to talk to during the download was Whimzy, so maybe I'll still go out to the record store for old times sake.
It's a Small World, But I Wouldn't Want to Paint It
Steven Wright turned 59 yesterday. It seemed a shame not to look at some of his best lines.
I couldn't repair your brakes, so I made your horn louder.
just got out of the hospital. I was in a speed-reading accident. I hit a bookmark.
If Barbie is so popular, why do you have to buy her friends?
I watched the Indy 500, and I was thinking that if they left earlier they wouldn't have to go so fast.
Whenever I think of the past, it brings back so many memories.
I couldn't repair your brakes, so I made your horn louder.
I spilled spot remover on my dog. Now he's gone.
I used to work in a fire hydrant factory. You couldn't park anywhere near the place.
The sign said "eight items or less". So I changed my name to Les.
Sponges grow in the ocean. That just kills me. I wonder how much deeper the ocean would be if that didn't happen.
I went to a restaurant that serves "breakfast at any time". So I ordered
French Toast during the Renaissance.
French Toast during the Renaissance.
Subscribe to:
Posts (Atom)