Archive for May 2010
At last Drog understood the nature of the beast he was up against. … No creature without tentacles had ever developed true intelligence. That was Etlib’s Law, and it had never been disputed. In a battle between intelligence and instinctive cunning, intelligence always won. It had to. All he had to do was figure out how.
Robert Sheckley, “Hunting Problem”.
I was planning to tell about an exciting probability game problem, but I decided to postpone that and to tell instead about a much easier game. This is one of my favorite simple problems.
We are playing a game of Battleship. The enemy Battleship is located at some integer point A on the number line. It is moving at some constant integer velocity V, meaning on each turn its position changes by V units. Both A and V are unknown. Find a strategy that allows to sink the ship in a finite number of shots.
That wasn’t a very clear formulation so let me explain. Player 1 (P1) chooses an integer number A as the initial position of the ship, and some integer number V as the velocity. On each turn, Player 2 (P2) attempts to guess the current position of the ship. If the guess is correct, the ship is sunk and P2 wins. Otherwise, P1 moves the ship by V units, and the players continue to take turns. We want to find a strategy that allows P2 to sink the ship in a finite number of turns.
Here is how to approach and solve this problem.
The dealer shuffles a deck of cards, then begins to turn cards face up one-by-one. You can say “stop” at any moment, and if the next card is red – you win, and if it’s black – you lose.
It’s not difficult to prove that there is no winning strategy. No matter when you stop the process, you have an even chance.
In general, you cannot time the market http://en.wikipedia.org/wiki/Optional_stopping_theorem
In one of my next posts I’m going to tell about a much more exciting game, which is not a fair game though.
By the way, “martingale” is an anagram of “lame rating”