The Critical Line Volume 32

This month’s Critical Line puzzle is brought to you by Dan Mayoh, who presents a two-part probability question. Submit your solutions for your chance to win a $50 Dymocks book voucher!

Part 1:

R red and B black playing cards are shuffled together, with R > B. The shuffled deck is then dealt out one card at a time. After each card is dealt, define D as the cumulative number of red cards dealt minus the cumulative number of black cards dealt.

What is the probability that D is positive for the entire deck? Give your answer as a function of R and B.

Now, after I composed this and ran it by some people, it was brought to my attention that an equivalent problem has been asked and answered a long time ago, and is somewhat well known amongst mathematicians (which doesn’t surprise me at all).  I’ll share its more well-known name next month with the solution, but have decided to keep it as the challenge due to the variety of elegant ways to solve this.  For those that may have seen this already though, let me offer an additional challenge.

Part 2:

Essentially the same question, but with three types of cards instead of two, and for a specific set of values instead of a general case (as the general case is a little too challenging for this setting).

A deck of 16 playing cards is shuffled together, comprised of six hearts, five spades and five clubs.  The shuffled deck is then dealt out one card at a time.  What is the probability that after each card is dealt, the cumulative number of hearts dealt exceeds both the cumulative number of spades dealt and the cumulative number of clubs dealt?

To be in contention to win the book voucher, submit an answer to part 1.  For added glory, submit an answer to part 2 as well!

For your chance to win a $50 book voucher, send your solutions to ActuariesMag@actuaries.asn.au

 

Volume 30 solution – Oliver Chambers

We had three correct submissions this month: congratulations to Felix Zhu, Thomas Zhou, and Ean Chan. The recipient of this month’s book voucher is Felix Zhu.

PROBLEM

$$n > 10$$ coins lie in a line on a table. Initially all coins show heads. Two players, $$A$$ and $$B$$, take it in turns to find a block of $$10$$ consecutive coins with the leftmost coin showing heads and flipping those $$10$$ coins over (such that the heads show tails and vice versa). If a player is not able to make a move then they lose the game.

  • Show that the game always terminates
  • If Player $$A$$ may decide whether to play first or second. Is there a winning strategy? If so, what is it?

 

SOLUTION

  • There is a natural bijection between the state of the coins and a binary number where heads maps to 1 and tails maps to 0. This number is strictly decreasing (but non-negative) after each move so the game must terminate.
  • Number the coins from $$n$$ (left-most coin) to $$1$$ (right-most coin) and consider the coins at $$10k$$ for $$k = 1, …, \left\lfloor\frac{n}{10}\right\rfloor$$. Any legal move will flip exactly one of these coins, so after two moves the parity of the number of those coins is preserved. That means that if $$\left\lfloor\frac{n}{10}\right\rfloor$$ is odd then the first player will always have a legal move (i.e. the first player wins regardless of strategy). On the other hand, if $$\left\lfloor\frac{n}{10}\right\rfloor$$ is even then the first player will always lose. So Player $$A$$’s strategy is simply to check the parity of $$\left\lfloor\frac{n}{10}\right\rfloor$$ and chose to play first or second accordingly.

CPD: Actuaries Institute Members can claim two CPD points for every hour of reading articles on Actuaries Digital.

Comments

No comments.


Comment on the article (Be kind)

Your comment will be revised by the site if needed.