Puzzles

The Election

The Election

By Joshua Feldman

When not writing or grading puzzles for Contingencies, for the past few years I have had a second extracurricular actuarial activity take up my time:

I am the president of the Central State Actuarial Forum (CSAF), a proud affiliate of the Casualty Actuarial Society. While I was at first reluctant to run for office (my boss convinced me to run by telling me that if I volunteered I could have a mini-fridge in my office), I must say that I have enjoyed my time as an officer. Alas, all good things must come to an end, as my term as president expired in October. So starting this month someone else will lead the brave, great casualty actuaries from seven Midwestern states.

Normally, the CSAF has trouble recruiting volunteers to run for office. During my four years as an officer, not once have we had a contested election. But I have a feeling that things will change this time around! See, in my dreams I had a premonition that we would have not one, not two, but 10 people volunteer to take up my place as a CSAF officer. When it rains, it pours! While I would like to believe that my strong managerial skills encouraged lots and lots of new volunteers, I know deep down that most likely my stewardship of the CSAF likely wasn’t up to par, so a bunch of people stepped up to right the sinking ship…

No matter what their reasons, the CSAF had a dilemma on its hands, as we needed to figure out who will become the next president of our great organization. We all quickly realized that all 10 candidates were more than qualified for the position, and everyone in the room would be happy with anyone taking over. So instead of having an election and forcing everyone to choose sides, we all agreed to let chance decide who would take over.

Someone suggested that we use a 10-sided die to figure out the winner, but that idea got voted down quickly, as 10-sided dice are notorious for being biased and not random. Someone else suggested we use Excel to create a random number, but no one trusted that the seed would indeed be random. Finally, as my last move as president, I suggested the following. We will arrange all 10 candidates (named Andrea, Bob, Courtney, Dan, Edith, Frank, Grace, Howard, Ingrid, and Jeremy) in a circle. I will then flip a fair coin. If it turns up heads, then the person on my left—Andrea—will flip the coin. If it turns up tails, then the person on my right—Jeremy—flips the coin. If Andrea flips the coin next, if it is heads, Bob will have the next turn; if tails, Jeremy is up. Similarly, if Jeremy flips next, if it is heads, Andrea will flip next, and if it is tails, Ingrid will do the honors. We will continue this process of flipping coins and determining who will next flip the coin by its heads / tails outcome until everyone has flipped the coin at least once. The last person to flip the coin will become president.

After hearing this process, someone in the crowd asked what the probability was of each of the 10 people winning the election. That is the problem for you, my readers, to solve.

What is the probability of each of the 10 candidates (Andrea, Bob, Courtney, Dan, Edith, Frank, Grace, Howard, Ingrid and Jeremy) to become president?

Bonus: Someone nefarious snuck in an unfair coin, such that it is now a 60% chance of landing heads, and a 40% chance of landing tails. How does this alter the probability of each of the 10 candidates to win the election?

NOTE: Normally most puzzles here are my own creations. This puzzle is an exception, as I got inspiration from Henk Tijm’s new book, Surprises in Probability. For those looking for a challenging book on probability, feel free to check it out. Don’t let the book’s short length and pretty cover pictures fool you, the chapters are not bedtime stories! This book is dense and rigorous. I have a feeling lots of fellow puzzlers would enjoy the book.

 

Solution to Previous Puzzles: Sum of Cubes Equals Square of Sum

The problems centered around solutions in positive integers to the Diophantine equations

a13 + a23 + … + an3 = (a1 + a2 + … + an)2                 (1)

There are the well-known solutions:

13 + 23 + … + n3 = (1 + 2 + … + n)2                    (2)

Problem 1. Show that there are exactly 2 solutions to (1) for n = 3. (i.e., exhibit the two solutions and show that there are no others.)

Answer (Partial): <1, 2, 3> and <3, 3, 3>

Problem 2. Show that, in addition to (2), there is a second general solution to (1) for all n.

Answer: Everyone answered: n copies of n, e.g., <3. 3, 3> for n=3 and <4, 4, 4, 4> for n=4.

The proof is that n(n3) = n4 = (n × n)2. I’m still looking for others; I wonder if there are any.

Problem 3. Find all the solutions to (1) for n = 4..

Answer (Partial): <1, 2, 2, 4>, <1, 2, 3, 4>, <2, 2, 4, 4> and <4, 4, 4, 4>

(While the wording of Problem 3 is not the same as Problem 1, the description of the Problem 1 was fleshed out in a parenthetical phrase to remind solvers they cannot say they have all the solutions to a problem unless they can show there are no others.)

The way to show there are no more solutions is to test all sets of integers until you or your computer gets tired and then demonstrate that what’s left can’t possibly work. The testing phase is typically a list up to some limit, say a large value of an, while the demonstration is a proof that above that limit the sum of the cubes is always greater than the square of the sum. As the limit goes higher (for n fixed) the lists get longer but the demonstrations tend to get easier. For Problem 1 solvers used limits up to 10 and for Problem 3, up to 99.

Problem 1 (Completion), Using a limit of 4 means that 6C3 = 20 cases need to be individually tested by hand or on a spreadsheet. To prove that 4 is adequate, we assume that c ≥ 5  and c  ≥ ba ≥ 1. Then 2(a + b) ≤ 4c.

Case A. b ≥ 3: a3 + b3 + c3 > (a+b)2 + (c–1)c2 + c2 (a+b)2 + 4c2 + c2 (a+b)2 + 2(a+b)c + c2 = (a+b+c)2. (The 1st inequality was demonstrated in the original problem statement.)

Case B. b ≤ 2: There are just three cases to check: <1,1,5>, <1,2,5> and <2,2,5>, which can easily be done by hand. However, these do not deal with <1. 1, c> etc. in general. In these and other cases, we could use the following Lemma: If f(x) = a3+…+x3 – (a+…+x)2 >0 and x≥n (number summands), then f(y) is positive for all y≥x. Proof: The derivative of f(x) is positive for x≥n. The lemma proves that <1, 1, c>, <1, 2, c> and <2, 2, c> satisfy f(c)>0 for c ≥ 5.

Problem 3 (Completion): Using a limit of 6 means that 8C4 =70 cases need to be tested. To prove that 6 is adequate, we assume d ≥ 7  and d ≥ c ≥ b ≥ a ≥ 1. Then 2(a+b+c) ≤ 6d.

Case A. c5: From above a3 + b3 + c3 + d3 > (a+b+c)2 + (d–1)d2 + d2 (a+b+c)2 + 6d2 + d2 ≥  (a+b+c)2+ 2(a+b+c)d + d2 = (a+b+c+d)2

Case B. c4: There are 35 additional cases to test. (Some can be skipped by using the Lemma or by other means.)

 

Solvers

Robert Bartholomew, Bob Byrne, Samantha Casanova, Andrew Dean*, Bill Feldman[1], Rui Guo, Clive Keatinge,
David Lovit Lincoln Financial Problem Solving Group,
David Promislow, Tomasz Serbinowski, John Snyder,
Mark Spong, Al Spooner

 

 

[1]Did not complete Problem 3.

Print Article
Next article Mapping Your Way
Previous article Simplicity Through Complexity

Related posts