Archive for combinatorics

Bernoulli factory in the Riddler

Posted in Books, Kids, R, Statistics with tags , , , , , , , , , , on December 1, 2020 by xi'an

“Mathematician John von Neumann is credited with figuring out how to take a p biased coin and “simulate” a fair coin. Simply flip the coin twice. If it comes up heads both times or tails both times, then flip it twice again. Eventually, you’ll get two different flips — either a heads and then a tails, or a tails and then a heads, with each of these two cases equally likely. Once you get two different flips, you can call the second of those flips the outcome of your “simulation.” For any value of p between zero and one, this procedure will always return heads half the time and tails half the time. This is pretty remarkable! But there’s a downside to von Neumann’s approach — you don’t know how long the simulation will last.” The Riddler

The associated riddle (first one of the post-T era!) is to figure out what are the values of p for which an algorithm can be derived for simulating a fair coin in at most three flips. In one single flip, p=½ sounds like the unique solution. For two flips, p²,(1-p)^2,2p(1-p)=½ work, but so do p+(1-p)p,(1-p)+p(1-p)=½, and the number of cases grows for three flips at most. However, since we can have 2³=8 different sequences, there are 2⁸ ways to aggregate these events and thus at most 2⁸ resulting probabilities (including 0 and 1). Running a quick R code and checking for proximity to ½ of any of these sums leads to

[1] 0.2062997 0.7937005 #p^3
[1] 0.2113249 0.7886753 #p^3+(1-p)^3
[1] 0.2281555 0.7718448 #p^3+p(1-p)^2
[1] 0.2372862 0.7627143 #p^3+(1-p)^3+p(1-p)^2
[1] 0.2653019 0.7346988 #p^3+2p(1-p)^2
[1] 0.2928933 0.7071078 #p^2
[1] 0.3154489 0.6845518 #p^3+2p^2(1-p)
[1] 0.352201  0.6477993 #p^3+p(1-p)^2+p^2(1-p)
[1] 0.4030316 0.5969686 #p^3+p(1-p)^2+3(1-p)p^2
[1] 0.5

which correspond to

1-p³=½, p³+(1-p)³=½,(1-p)³+(1-p)p²=½,p³+(1-p)³+p²(1-p),(1-p)³+2(1-p)p²=½,1-p²=½, p³+(1-p)³+p²(1-p)=½,(1-p)³+p(1-p)²+p²(1-p)=½,(1-p)³+p²(1-p)+3p(1-p)²=½,p³+p(1-p)²+3(p²(1-p)=½,p³+2p(1-p)²+3(1-p)p²=½,p=½,

(plus the symmetric ones), leading to 19 different values of p producing a “fair coin”. Missing any other combination?!

Another way to look at the problem is to find all roots of the 2^{2^n} equations

a_0p^n+a_1p^{n-1}(1-p)+\cdots+a_{n-1}p(1-p)^{n-1}+a_n(1-p)^n=1/2

where

0\le a_i\le{n \choose i}

(None of these solutions is rational, by the way, except p=½.) I also tried this route with a slightly longer R code, calling polyroot, and finding the same 19 roots for three flips, [at least] 271 for four, and [at least] 8641 for five (The Riddler says 8635!). With an imprecision in the exact number of roots due to rather poor numerical rounding by polyroot. (Since the coefficients of the above are not directly providing those of the polynomial, I went through an alternate representation as a polynomial in (1-p)/p, with a straightforward derivation of the coefficients.)

parking riddle

Posted in Books, Kids, pictures, R, Statistics, Travel with tags , , , , , , on October 23, 2020 by xi'an

The Riddler of this week had a quick riddle: if one does want to avoid parallel parking a car over a six spot street, either the first spot is available or two consecutive spots are free. What is the probability this happens with 4 other cars already parked (at random)?

While a derivation by combinatorics easily returns 9/15 as the probability to fail to park, a straightforward R code does as well

 l=0
  for(t in 1:1e6){
  k=sort(sample(0:5,4))
  l=l+1*(!!k[1]|3%in%diff(k)|!k[4]%%3)}

since

 
> round(choose(6,2)*F/1e6)
[1] 10

Le Monde puzzle [#1121]

Posted in Books, Kids with tags , , , , on December 17, 2019 by xi'an

A combinatoric puzzle as Le weekly Monde current mathematical puzzle:

A class of 75<n<100 students is divided at random into two groups of sizes a and b=n-a, respectively, such that the probability that two particular students Ji-ae and Jung-ah have a probability of exactly 1/2 to be in the same group. Find a and n.

(with an original wording mentioning an independent allocation to the group!). Since the probability to be in the same group (under a simple uniform partition distribution) is

\frac{a(1-1)}{n(n-1)}+\frac{b(b-1)}{n(n-1)}

it is sufficient to seek by exhaustion values of (a,b) such that this ratio is equal to ½. The only solution within the right range is then (36,45) (up to the symmetric pair). This can be also found by seeking integer solutions to the second degree polynomial equation, namely

b^\star=\left[ 1+2a\pm\sqrt{1+8a}\right]/2 \in \mathbb N

numbers of numbers with numbers of their numbers

Posted in Statistics with tags , , , on April 6, 2019 by xi'an

A funny riddle from The Riddler where the number of numbers that indicate the numbers of their numbers is requested. By which one means numbers like 22 (two 2’s) and 21322314 (two 1’s, three 2’s, two 3’s and one 4), the convention being that “numbers consist of alternating tallies and numerals”. And that numerals are “tallied in increasing order”. A reasoning based on the number of 1’s, from zero (where 22 seems to be the only possibility) to six (where 613223141516171819 is the only case) leads to a total of 59 cases (unless zero counts as an extra case) and a brute force R exploration returns the same figure:

for (t in 1:1e5){
  az=sample((0:6),9,rep=TRUE)
  count=rep(TRUE,9)
  for (i in 1:9) count[i]=(sum(az==i)+(az[i]>0))==az[i]
  nit=0
  while ((min(count)==0)&(nit<1e2)){      
    j=sample((1:9)[!count],1)      
    az[j]=(sum(az==j)+(az[j]>0))
    nit=nit+1}
  if (min(count)==1) solz=unique.matrix(rbind(solz,az),mar=1)}

The solution published on The Riddler differs because it also includes numbers with zeros. Which I find annoying to the extreme because if zeroes are allowed then every digit not in the original solution should appear as multiplied by 0, which is self-contradictory… For instance 22 should be 012203…09, except then there is one 1, one 3, and so on.

 

Le Monde puzzle [#1073]

Posted in Books, Kids, R with tags , , , , , , on November 3, 2018 by xi'an

And here is Le Monde mathematical puzzle  last competition problem

Find the number of integers such that their 15 digits are all between 1,2,3,4, and the absolute difference between two consecutive digits is 1. Among these numbers how many have 1 as their three-before-last digit and how many have 2?

Combinatorics!!! While it seems like a Gordian knot because the number of choices depends on whether or not a digit is an endpoint (1 or 4), there is a nice recurrence relation between the numbers of such integers with n digits and leftmost digit i, namely that

n⁴=(n-1)³, n³=(n-1)²+(n-1)⁴, n²=(n-1)²+(n-1)¹, n¹=(n-1)²

with starting values 1¹=1²=1³=1⁴=1 (and hopefully obvious notations). Hence it is sufficient to iterate the corresponding transition matrix

M= \left(\begin{matrix}0 &1 &0 &0\\1 &0 &1 &0\\0 &1 &0 &1\\0 &0 &1 &0\\\end{matrix} \right)

on this starting vector 14 times (with R, which does not enjoy a built-in matrix power) to end up with

15¹=610, 15²= 987, 15³= 987, 15⁴= 610

which leads to 3194 different numbers as the solution to the first question. As pointed out later by Amic and Robin in Dauphine, this happens to be twice Fibonacci’s sequence.

For the second question, the same matrix applies, with a different initial vector. Out of the 3+5+5+3=16 different integers with 4 digits, 3 start with 1 and 5 with 2. Then multiplying (3,0,0,0) by M¹⁰ leads to 267+165=432 different values for the 15 digit integers and multiplying (0,5,0,0) by M¹⁰ to. 445+720=1165 integers. (With the reassuring property that 432+1165 is half of 3194!) This is yet another puzzle in the competition that is of no special difficulty and with no further challenge going from the first to the second question…