Puzzle #4: Working Days

Calculating the number of days between two arbitrary dates is doable for humans and trivial on modern computers. However, calculating the number of working days: Mondays through Fridays, is more complicated. In this puzzle you are asked to devise an algorithm for doing this. It is something you can do on the back of a napkin, so you don’t need anything besides pen, paper and the rational part of your brain.

Problem:
Given two dates d_{1}, d_{2} where d_{2}>d_{1}, what is the number of workdays w between these two dates? Assume that only Saturdays and Sundays are not workdays: holidays can be ignored.

You may use the following definitions augmented with any standard mathematical functions, like div and min.

  • d is a date
  • Subscripts are used to indicate different dates: d_{1},d_{2}\cdots d_{n}
  • d_{x}-d_{y} yields the number of days between two dates. This is negative if d_{x}<d_{y} and zero if the dates are identical
  • weekday\left(d\right) gives the day of the week for the given date as a number (1 = Monday, 2 = Tuesday, …, 7 = Sunday)
  • weeknumber\left(d\right) gives the number of the week for the specified date (in the range 1 up to including 53)
  • workdays=\left{ 1,2,3,4,5\right} is the set of numbers that represent working days (a subset of the domain of the weekday function)

Try to work out a solution first, then expand mine below.

Solution
There are really two cases to consider.

If both days are in the same week:
weeknumber\left(d_{1}\right)=weeknumber\left(d_{2}\right)\Rightarrow d_{2}-d_{1}\leq7,
the solution might seem simple: w=d_{2}-d_{1}. This will work provided that both dates have a weekday less than or equal to five. If this is not the case, we need a more complex function: w=min\left(weekday\left(d_{2}\right),5\right)-min\left(weekday\left(d_{1}\right),5\right)+1. The min function returns the lesser of its two arguments (or either one in case they are equal). The +1 is to count the end date as a whole day. Note that we exploit here the fact that the workdays form a continuous range (1–5).

If both days are not in the same week:
weeknumber\left(d_{1}\right)\neq weeknumber\left(d_{2}\right),
then we must devise a way to find the number of weekends in between the two dates (each weekend subtracts two days from the interval \left[d_{2},d_{1}\right]). We can do this in three steps:

  1. Determine if the starting day is in a workweek: 5-weekday\left(d_{1}\right)\geq0. If so, then set this as the initial count: c=\left(5-weekday\left(d_{1}\right)\right), otherwise set c=0.
  2. c now covers the number of working days in the first week of the range. To find the number of remaining days we first subtract 7-weekday\left(d_{1}\right) days from the days between the dates d_{2}-d_{1}. We wil define this as: r=\left(d_{2}-d_{1}+1\right)-\left(7-weekday\left(d_{1}\right)\right).
  3. The number of weekends must be div\left(r,7\right), since each weekend consists of two days, we must subtract this twice, giving: w=c+r-\left(2\cdot div\left(r,7\right)\right). The div function is an integer division yielding a whole number. It is equivalent to \leftl\floor x/y\rightr\floor (the floor of a division, in this case between r and 7).

These steps are the full solution for the case where the weeks are not equal. Below are some examples of the method presented. However, perhaps you’ve come up with a simpler or more elegant solution? Let me know in the comments below.

Examples:
For the number of working days between d_{1}=16-02-2009 (weekday 1) and d_{2}=18-02-2009 (weekday 3): since these are within the same week (week 8), the number of working days is:

w=min\left(3,5\right)-min\left(1,5\right)+1=3-1+1=3

For the number of working days between d_{1}=16-02-2009 (weekday 1) and d_{2}=22-02-2009 (weekday 7): these are also within the same week (week 8), but the end date is in the weekend. Still this should work:

w=min\left(7,5\right)-min\left(1,5right)+1=5-1+1=5

For the number of working days between d_{1}=16-02-2009 (weekday 1) and d_{2}=25-02-2009 (weekday 3): these are not within the same week, thus we must use the three step approach:

c=\left(5-1\right)=4
r=\left(25-16+1\right)-\left(7-1\right)=10-6=4
w=4+4-\left(2\cdot0\right)=8

Here we see that the last part of the formula has no effect. This is always true for adjacent weeks, since div\left(r,7\right)\geq1 only if r\geq7.

So, now for non-adjacent weeks:
For the number of working days between d_{1}=09-02-2009 (weekday 1) and d_{2}=25-02-2009 (weekday 3):

c=\left(5-1\right)=4
r=\left(25-9+1\right)-\left(7-1\right)=17-6=11
w=4+11-\left(2\cdot1\right)=13

Puzzle #3: Boys and Girls

Problem:
Assume a country where every family wants to have a boy and continues having babies until they actually have one. We consider only one generation. The probability of having a boy or a girl is always the same. After some time has passed, what is the ratio between boys and girls in the country? Try to work it out yourself and then expand the solution below.

Solution
The right answer to this question can be determined by intuition. However, does your intuition tell you that there will be more boys and less girls eventually? That is what most people would say. However, let’s see if we can solve it mathematically.

We know that for each birth the probability of a boy or a girl must be equal and is thus fifty percent for each. It is perhaps best to think of this as flipping a coin with half a chance on heads and the other half on tails.

Let’s first break it down by analysing what must be true at all times:

  1. All families always have at least 1 boy.
  2. All families must have somewhere between (inclusive) 0 and \infty1 girls.

We can further break down the second question in infinitely many sub-questions of the form: “How many families have n girls?”. Where n ranges between 0 and \infty. A more visual way to express this is by coding girls with a G, boys with a B and then determining the likelihood of existence of each of the following family compositions (not counting the father and mother):

  • B
  • GB
  • GGB

Well, we already established that the probability of having either a boy or girl is fifty percent. Hence, the probability of a family with only a boy is fifty percent (equivalent to a family with zero girls), a family with one girl and one boy: twenty five percent, and a family with two girls and one boy: twelve point five percent, et cetera. Based on this we can calculate the number of girls NG as follows:

NG=\frac{1}{2}\cdot0+\frac{1}{2}\cdot\frac{1}{2}\cdot1+\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{2}\cdot2+\ldots

If you find this difficult to follow, keep in mind that each family that does not have a boy yet will, at the next birth, again have a fifty/fifty chance on a boy. However, as there are more births in the same family the probability of not having a boy goes down with each girl that joins the family. Realise that this is not because the independent probability of having a girl or boy changes, but the probability of having ever longer strings of girls being born in the same family goes down as the family grows larger. This problem is in fact equivalent to flipping a fair coin and determining the probability of heads or tails over an infinite set of trials also known as a Bernoulli trial.

People familiar with mathematics and probability have probably noticed that the above approximation can more accurately be written as an infinite series:

NG=\sum_{n=1}^{\infty}\frac{1}{2^{n}}
where n is the number of families.

So, what is the outcome of this? The number of girls approaches 1 as we let n approach infinity. We also know the number of boys in each family must be at least 1. Hence, the counter-intuitive answer is that most families will consist of one boy and one girl.

Some people will now draw the conclusion that the ratio must be 1:1 as well. However, that conclusion is controversial. Economist Steven Landsburg went as far as to offer a public bet on this. His main point is that even if the main variables (boys and girls) have an expected difference of zero, you can not conclude that they have a ratio of 1 to 1.

Mathematically the expected value of boys and girls are both one:
E\left(B\right)=1
E\left(G\right)=1

However, the question is what is the expected ratio of girls to the child population:
E\left(G/\left(G+B\right)\right)=?

The approximation given by Landsburg is:
E\left(G/\left(G+B\right)\right)=\frac{1}{2}-\frac{1}{4\cdot n}
where n is the number of families.

This seems like a more satisfactory answer then saying the ratio is 1:1, as it captures the value of n very explicitly. Based on this, we can safely say that the right answer is: for a very large population the ratio will approach 1:1, but never actually reach it.

There are many other people that have given perspectives on this problem, and more thorough mathematical background, like here and here. However, some of them also make the original problem much more complicated than it was. Other sources I used to compile this article are here and here.

Notes:
1) Infinity – of course: this is a theoretical limit

Puzzle #1: The Student Admission Problem

Background: I will occasionally present a small (mathematical) puzzle here. These are a tribute to the column “Vuiks Verhandelingen”, written by Kees Vuik which regularly appeared in the Dutch PCM Magazine nearly a decade ago. Sometimes I may think of them myself, and sometimes they may come from elsewhere.

Let’s get started: 114 students applied for a specific study, only 100 were eventually admitted by lottery. Among the 114 students were 5 foreign students. However, none of these foreigners were among the 100 that were admitted. Intuitively this seems quite unlikely. But how unlikely is it really? Were the foreigners intentionally not admitted?

Your task: find the probability that the 5 foreign students were left out due to chance. This can be solved with basic knowledge of probability and set theory. First try it yourself, then click below to expand the solution and check your answer.

Solution

Tip: if you are not too familiar with mathematical notation, don’t be intimidated by it: it’s just a way to formally write things down, and the notation here should be easy to follow. I’ve added some footnotes to help: hover over them with your mousepointer to see an explanation.

Definitions
We start with some generic definitions:

  • S is the set of all students that applied.
  • F is the subset of S which is foreign.
  • n is the number of students we may select from S (without replacement1).
  • The resulting selection we call set L (where L is a subset of S with cardinality2 n )

Let’s fill out the variables above for this specific case:

  • There are 114 students in total: #S=114
  • Of which 5 are foreigners: F\subset S\wedge#F=5 3
  • We may select 100 students: n=100

Problem:
What is the probability that we select no foreign student when we choose 100 students out of the 114 that applied? Formal: what is the probability that the intersection of F and L is empty?: P\left(F\cap L=\varnothing\right)

Solution:

  1. We know that there are \binom{#S}{n} ways4 in which we can select n students from the #S (without replacement).
  2. There are \binom{#F}{k} ways to select k students from the foreign subset.
  3. Given (2) there are \binom{#S-#F}{n-k} ways to select the remaining n - k students.
  4. Combining (1-3) we get:P\left(F\cap L=\varnothing\right)=\frac{\binom{#F}{k}\cdot\binom{#S-#F}{n-k}}{\binom{#S}{n}}

In this last step we effectively state that the probability is the number of ways in which we can select k and n - k students, relative to the total number of possible selections we can make. It is a generic solution for any set sizes, for this specific instance we take the problem specific values and simply substitute them:

P\left(F\cap L=\varnothing\right)=\frac{\binom{5}{0}\cdot\binom{114-5}{100-0}}{\binom{114}{100}}=\frac{\binom{5}{0}\cdot\binom{109}{100}}{\binom{114}{100}}=\frac{\binom{109}{100}}{\binom{114}{100}}\thick\approx1.36\cdot10^{-5}

All the values are as specified in the problem specific definition. The value of k is 0, since we are interested in the probability of selecting 0 students from the Foreign group. We see that the problem simplifies, since \binom{5}{0}=1.

We can conclude that the probability of selecting none of the 5 foreign students is quite low: 0.00136 %

The probability that the lottery was unfair can be deduced from this:
P\left(F\cap L\neq\varnothing\right)=1-P\left(F\cap L=\varnothing\right)=1-1.36\cdot10^{-5}=0.9999864

Which is 99.99864%. Indeed, it is very likely that at least one foreign student would have been selected. Hence we can state that it is likely that the lottery applied was unfair in this case and that the probability of a foreign student of being selected must have been much lower than that of a local student, or even zero.

Notes:
1) This means that the same student can not be selected twice. So, while each student initially has a chance of 1/114 to be picked, after the first pick this will be 1/113, then 1/112, et cetera.
2) A fancy way of saying: size
3) From left to right: F is a subset of S and there are 5 students in F
4) This is binomial notation, that should be interpreted as: \binom{n}{k}=\frac{n!}{k!\cdot\left(n-k\right)!}.
With:

  • n!=prod_{r=1}^{n}r=n\cdot\left(n-1\right)\cdot\left(n-2\right)\ldots1
  • 0!=1