About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
August 2024 - Solution
August 2024 Solution:
The answers are 205 and 60694.
This problem is a relativly simple case of a Markov chain: Assume for the general case we
have sets with
elements each (for our problem we have
for the standard and
for the bonus).
We have a state for every number
of sets we already guessed, and we
compute the transition probability between states:
is the probability of transition
from
to
. Denote the expected time to hit
starting from
by
, then
(as a special case of the general theorem about hitting times in Markov chains) we have the
following equations:
This is simplified by noting that for
since we cannot "unguess" a set. So we can write:
Leading to the solution
We are interested in the expected time to reach from
, hence we iteratively
compute
with
being our result.
It remains to compute the transition probabilities , i.e. to solve the combinatorial
problem "Given n-i sets to guess, each with k elements, what is the probability of guessing
exactly
?"
The combinatorial object being counted is the number of ways to partition into
sets, with no order between the sets. If we do consider the order
between sets, this is the standard problem of permutations with repetition (we permute the
set designations - the "colors"), which is solved by the formula
We
divide it by
to accomodate for the lack of order between sets and obtain the value
.
Given at least correct "guesses" it means there remain
sets whose elements are
freely distributed, hence there are
partitions which guess specific
sets. To
count the number of guesses where exactly
correct guesses were made we use the
inclusion-exclusion principle:
Where is the number of ways to choose the specific
sets correctly guessed,
and the sum is a standard use of inclusion-exclusion to find the number of guesses (for the
remaining
sets) where no correct guess was made.
This gives us the probability of guessing exactly of the
possible sets:
and hence,
, with the above
hitting expectation time equations giving the solutions.
The following (inefficient) code immediately solves both the standard and the bonus problems:
from math import factorial, comb
def F(n, k):
return factorial(n*k) // (factorial(k)**n * factorial(n))
def G(n,k,j):
return comb(n,j)*sum([(-1)**r*comb(n-j,r)*F(n-j-r,k) for r in range(n-j+1)])
def p(i,j, n, k):
return G(n-i,k,j-i)/F(n-i,k)
def h(i, n, k):
return (1+sum([p(i,j,n,k)*h(j,n,k) for j in range(i+1,n)]))/(1-p(i,i,n,k))
print("(4,4) problem:", float(h(0,4,4)))
print("(10,5) problem:", float(h(0,10,5)))