The birthday paradox is a fairly well-known but unintuitive observation that although there are normally 365 days in a year (for simplicity, ignoring leap years and assuming a uniform distribution for birthdays), with as few as 23 people it is more likely than not that two of them will share a birthday. One of my teammates proposed an inverse of this problem: what is the minimum number of people are needed so that it is more likely than not that it is someone’s birthday every day?
Modelling A Specific Instance
There’s a lot to take in here, so let’s try to solve a simpler problem first. We could attempt to solve: given a specific number of people, how would we calculate the probability that it is someone’s birthday every day? If we have this method, we can reconstruct the answer to the original problem via a search algorithm.
The more general problem here would be: suppose we have 
Algorithmic Ideation
Base Case Analysis
If 
We can now analyze 
- The first person to draw an event will get a novel event. This leaves 3 people to draw events, and 2 out of 3 events undrawn. We can call this state
.
- The second person to draw an event will get a novel event with probability 2/3, putting us in the state
. Alternatively, he/she will draw the same event as the first person with probability 1/3, getting us in the state
.
- If we’re in
.
- If we’re in
- If we’re in
More generally, we can model the problem using a state machine (a technique which I discussed two and a half years ago). The states of this machine can be written as 3-tuples 
For 
Recurrence Relations
We can define 
. We are already in a success state by definition.
. If everyone has drawn an event and there are still events that haven’t occurred, there is no chance for us to draw those events.
That’s all we need, and we can look at the recursive case. In the state 
Notice that these states are well-formed, since we handled the 
Solving The Specific Instance
The answer to our original problem, for a given number of people 
private static double findSuccessProbability(long remainingPeople, long remainingEvents, long totalEvents) {
if (remainingEvents == 0) {
return 1.0;
}
if (remainingPeople == 0) {
return 0.0;
}
double probabilityOfNewEvent = ((double) remainingEvents) / totalEvents;
double successProbabilityOnNewEvent = findSuccessProbability(remainingPeople - 1, remainingEvents - 1, totalEvents);
double successProbabilityOnOldEvent = findSuccessProbability(remainingPeople - 1, remainingEvents, totalEvents);
return probabilityOfNewEvent * successProbabilityOnNewEvent
+ (1 - probabilityOfNewEvent) * successProbabilityOnOldEvent;
}
We can test this and verify that indeed 
One solution here is to use memoisation. The naive version written above ends up computing the answer for the same state potentially exponentially many times, but we can cache the results of previous computations and use them. This could be done with a map with the 3-tuple as a cache key; alternatively, a bottom-up dynamic programming solution can be written, since there’s a clear order in which we process the subproblems. In any case, these methods should get the runtime down from exponential to 
Reconstructing The General Solution
We want to find the smallest 
public static void main(String[] args) {
long numPeople = 365;
double successProbability = findSuccessProbability(numPeople, 365, 365);
while (successProbability <= 0.5) {
numPeople++;
successProbability = findSuccessProbability(numPeople, 365, 365);
}
System.out.println(numPeople);
}
This gives us our answer: 2287. We have 
This approach looks a bit primitive – and normally we’d use a modified binary search where we first search for an upper bound via something that grows exponentially, and then binary search up to our bound. This works, since 
However, for this specific problem and more generally for recurrences where we end up reducing parameters by 1, we still need to burn through almost all of the smaller subproblems we skip over by isolating the bound, so it won’t actually give us that much here.
Usually when working with recurrences it is nice to find a closed-form solution for our expression (i.e. we have a general expression for 
and strategies 
with each 
being non-empty and a subset of 
. We also require that 
, otherwise not all achievements are achievable. The goal is to identify some set of strategies we need to deploy 
such that 
. Trivially, picking everything is possible, but it’s very unlikely that that’s going to be minimal.
strategies or fewer?) is NP-complete. Clearly, we can obtain a solution that is worst-case exponential in 
by iterating through each possible subset of 
, checking if it satisfies the criteria and remembering the best solution we’ve seen so far. There’s a little dynamic programming trick we can do to memoise partial achievement states (e.g. I can get to the state where I have the first 8 achievements and no others using two runs with one strategy but three with another; I’ll always pick the first). This achieves a solution exponential in 
but linear in 
, which is an improvement. We can also try to pre-process the input for 
and we seek to minimise the total weight of the strategies we pick. If we assign a strategy a given probability of success 
following standard geometric distribution results. The dynamic programming based algorithm still works if we keep track of weights instead of number of sets.
. There is a DP-based approach where one can keep track of the number of stone blocks that slashes this to 
which would probably be enough. With more clever approaches it’s possible to knock the time complexity down to 
– and that’s probably optimal as any less would involve not actually reading some parts of the grid.
, we want to return a suitably ordered list of words ![S = \left[ l^+ \right]](https://s0.wp.com/latex.php?latex=S+%3D+%5Cleft%5B+l%5E%2B+%5Cright%5D+&bg=ffffff&fg=000&s=0&c=20201002 "S = \left[ l^+ \right]")
, that satisfies the following properties:
is included in the game’s dictionary.
.
, 
is used in a word before or on position 
.![L = \left[ (A,3), (B_1,1), (B_2,1), (E, 1) \right]](https://s0.wp.com/latex.php?latex=L+%3D+%5Cleft%5B+%28A%2C3%29%2C+%28B_1%2C1%29%2C+%28B_2%2C1%29%2C+%28E%2C+1%29+%5Cright%5D&bg=ffffff&fg=000&s=0&c=20201002 "L = \left[ (A,3), (B_1,1), (B_2,1), (E, 1) \right]")
, and the dictionary recognises both 
and 
.
where 
are sets of the remaining clue words our own team has, words the enemy team has, and the neutral words, 
is the assassin, 
is the history of the game, and 
and 
are preference functions of the form 
, returning an ordered list 
. 
is a clue meaning that a given team gave a clue word and hinted that some number of cards was relevant. This already abstracts two difficult parts away – ordering the clues, and determining how many of the top preferences to pick.
each team has a persistent preference function that returns an ordered list of 
. The preference functions during the game then return the subsequence of that list that contains strictly the words still left in the game. This of course doesn’t take into account past information or clues from the other team.
as a prefix. A state is losing if all moves in that state produce a state which is winning for the opposing team.
as the maximum number of buckets distinguishable with 
trials and 
buckets to be given to no pigs, since with one fewer trial we can distinguish between them. For each of the pigs present, we need to prepare to continue the investigation with one fewer trial and one fewer pig, hence 
.
was somewhere in the 800s, which established that strategies based on risking one pig in every round apart from the last would be insufficient. Thinking a little more about it, I realised that in the extreme case, you could always have a special bucket each round that you gave to all pigs – if they all died that round, we would know that bucket was poisoned. However, you couldn’t have more than one of these per round – if they all died, you wouldn’t know which bucket was the cause.
. I was surprised to see how much additional discriminatory power five pigs had, though four wouldn’t be sufficient. Interestingly, five pigs and three periods were sufficient. The general closed form solution is simply 
and our argument provides a method for actually identifying the relevant bucket.
many possibilities, and there are 
. Clearly 
so four pigs isn’t enough; also, this expression matches the value obtained by our recurrence-based method, suggesting that that is indeed optimal.
nondeterministically returns either a or b. We can thus simply pick 
and 
, and add these statements. Finally, we would want to return 
. Some care needs to be taken with the implementation (for example, one must handle the case where a variable is only possibly modified correctly). This should, for the above block of code, yield:
