so long, and thanks for all the quests

The Riddler, which I have followed for many years, has been discontinued by FiveThirtyEight, but its producer, Zach Wissner-Gross, has launched a personal website to keep considering a weekly mathematical puzzle. The Fiddler on the Proof! Expect thus more ‘Og entries in this category!

another riddle

A riddle on The Riddler that pertains to game theory [and does not truly require coding]:

Ten pirates have ten gold pieces to divide and each have a unique rank, from the captain on down. The captain puts forth the first plan to divide up the gold, whereupon everyone votes. If at least half the pirates vote for the plan, it is enacted, and the gold is distributed accordingly. If the plan gets fewer than half the votes, however, the captain is killed, the second-in-command is promoted, and the process starts over.

Pirates always vote by the following rules, with the earliest rule taking precedence in a conflict:

1. Self-preservation: A pirate values his life above all else.
2. Greed: A pirate seeks as much gold as possible.
3. Bloodthirst: Failing a threat to his life or bounty, a pirate always votes to kill.

Under this system, how do the pirate divide up their gold?

An obviously final configuration is when there are only two pirates left since whatever division the first pirate proposes, including the one where he gets all the coins, the second (and last) one cannot oppose. Hence the last pirate must avoid reaching a two person configuration. On the opposite the one-to-last pirate should aim at this solution, but he is the only one! This means that for any configuration but one the last and second to last pirates will outvote the one to last. Meaning that the optimum for the second to one pirate is a partition of (9,0,1). Moving to the general case, when there remains 2p crew members, the pirate in command must secure a positive vote from  (p-1) other pirates below him, which means those (p-1) pirates must get one coin more than what they would get on the next round. This amounts to picking the (p-1) pirates with no reward on the next round and giving them one coin each, leading to a reward of 11-p for the current leader. When there remains 2p-1 crew members, the optimal solution is identical, namely to award one coin each for the (p-1) pirates with no reward on the next round. With a total of 10 pirates, the optimal configuration for the captain is to separate the 10 coins into (6,0,1,0,1,0,1,0,1,0).

another riddle with a stopping rule

A puzzle on The Riddler last week that is rather similar to an earlier one. Given the probability (1/2,1/3,1/6) on {1,2,3}, what is the mean of the number N of draws to see all possible outcomes and what is the average number of 1’s in those draws? The second question is straightforward, as the proportions of 1’s, 2’s and 3’s in the sequence till all values are observed remain 3/6, 2/6 and 1/6. The first question follows from the representation of the average

as the probability to exceed n is the probability that at least one value is not observed by the n-th draw, namely

3+(1/2)ⁿ+(2/3)ⁿ+(5/6)ⁿ-(1/6)ⁿ-(1/3)ⁿ-(1/2)ⁿ

which leads to an easy summation for the expectation, namely

3+(2/3)³/(1/3)+(5/6)³/(1/6)-(1/3)³/(2/3)-(1/6)³/(5/6)=73/10

an integer programming riddle

A puzzle on The Riddler this week that ends up as a standard integer programming problem. Removing the little story around the question, it boils down to optimise

200a+100b+50c+25d

under the constraints

400a+400b+150c+50d≤1000, b≤a, a≤1, c≤8, d≤4,

and (a,b,c,d) all non-negative integers. My first attempt was a brute force R code since there are only 3 x 9 x 5 = 135 cases:

f.obj<-c(200,100,50,25)
f.con<-matrix(c(40,40,15,5,
  -1,1,0,0,
   1,0,0,0,
   0,0,1,0,
   0,0,0,1),ncol=4,byrow=TRUE)
f.dir<-c("=","=","=","=","=","=")
f.rhs<-c(100,0,1,8,4)

sol=0
for (a in 0:1)
for (b in 0:a)
for (k in 0:8)
for (d in 0:4){
  cost=f.con%*%c(a,b,k,d)-f.rhs
  if (max(cost)<=0){ gain=f.obj%*%c(a,b,k,d)
if (gain>sol){
     sol=gain
     argu=c(a,b,k,d)}}}

which returns the value:

> sol
     [,1]
[1,]  425
> argu
[1] 1 0 3 3

This is confirmed by a call to an integer programming code like lpSolve:

> lp("max",f.obj,f.con,f.dir,f.rhs,all.int=TRUE)
Success: the objective function is 425
> lp("max",f.obj,f.con,f.dir,f.rhs,all.int=TRUE)$sol
[1] 1 0 3 3

which provides the same solution.

another riddle

A very nice puzzle on The Riddler last week that kept me busy on train and plane rides, runs and even in between over the weekend. The core of the puzzle is about finding the optimal procedure to select k guesses about the value of a uniformly random integer x in {a,a+1,…,b}, given that each guess y produces the position of x respective to y (less, equal, or more). If y=x at one stage, the player wins x. Optimal being defined as maximising the expected gain. After some (and more) experimentation, I found that, when b-a is large enough [depending on k], the optimal guess at stage i is b-f(i) with f(k)=0 and f(i-1)=2f(i)+1. For the values given on The Riddler, a=1,b=1000,k=9, my solution is to first guess at y=1000-f(9)=255 and this produces a gain of 380.31 with a probability of winning of 0.510, which seems amazingly large, but not so much when considering that 2⁹ is close to 500.