A Bit of Graph Theory

I’ve written a document which explains some basic graph theory. In particular, it poses a few puzzle questions related to planar graphs and then solves them using Euler’s Formula.

I tried to write it in a casual style. The idea was that it should be easy to read whilst not giving up any mathematical accuracy. Actually, I’m not sure the style works at all, but it was worth experimenting.

Thank you to Kris for some suggestions to improve it. A version suitable for A5 booklet printing is available on my website.

graph_preview

Click to view/download

Advertisements

Self-Referential Number Square #1 (Updated)

I’ve updated the first self-referential number square so that there isn’t any need for any additional clues at the bottom. It now looks as follows:

Suggested solution

A set of numbers such that when you remove one number, the rest can be arranged into two equal groups with the same sum

Suppose you have a set of 17 numbers with the property that if you remove any one of the numbers, the remaining can be split into two groups of 8 which sum to the same total. We will show that the numbers must all be equal.

If we have a set of 17 numbers with this property, then we can create another set of 17 numbers by subtracting a constant. So if a_1 \cdots a_{17} are one group of numbers with the property, then so is b_i = a_i - K.

Similarly, if a_i have the property, then so do c_i = K a_i, where K is a constant.

In particular, this means that we can shift it so that one of the numbers is zero.

To begin, let us assume the numbers in question are all integers. Let us take out the number which is zero. Therefore we get two groups which both sum to the same (integral) value, call it S. Therefore the sum of all the numbers T is simply 2S + 0. Therefore T is even.

Let us now take out another one of the numbers, call it k. So we get two groups of numbers again which sum to the same value, call it S’. So T = 2S’ + k. This implies that k is even, as is.

Therefore each of the numbers is even. But if that is the case, we can divide all the numbers by two to get another set of integers with the property. This process can be continued indefinitely, which is impossible unless all the numbers were zero to start with. Thus we conclude all the numbers were equal to zero. That means in the original case, before a constant was subtracted, they must have all been equal. (c.f. Proof by Infinite descent)

The case for rational numbers is simple, as you may just multiply all the rational numbers be a constant in order to make them all integers (for instance, by multiplying by the product of the denominators). Thus they are all equal.

The case for real numbers requires a trick. Denote the 17 numbers by a_i. These numbers generate a finite dimensional vector space over the rational numbers (of dimension at most 17, call it N). Therefore we can choose a basis (without the Axiom of Choice). Call this basis r_j, 1 \le j \le N \le 17.

Therefore each of the a_i can be written uniquely as a sum of the r_j multiplied by a rational number. Write [a_i]_j for the coefficient of r_j in this representation.

Fix j. Then the set of 17 numbers [a_i]_j, 1 \le i \le 17 form a set of rational numbers with the property that taking out any one of them allows the remaining to be rearranged into two groups with the same sum. This is because the set of 17 real numbers have this property, and whatever the two sums are, the r_j coefficients must be equal by the uniqueness of basis representations.

However, this implies by the above that the value of [a_i]_j is constant for different values of i.

Therefore all the coordinates are individually constant, and so the 17 numbers are all equal.

This problem is from Problems and Theorems in Classical Set Theory. Obviously, no use is actually made of the fact there are 17 numbers. In fact, no use is made of the fact that the two groups of numbers are equal sizes.

The Average of Average Speeds

I was giving a series of questions to complete from a friend. They were from a job application test. The questions were not very sophisticated, but the last one was as follows (verbatim):

A cyclist has to complete 2 laps of a track at an average of 60 Mph to beat the World record. If he completes the first lap at 30 Mph, what must his average speed be on the second lap for the record to be broken?

A naïve approach would be to say that if the first lap was at 30 mph, and the second lap at 90 mph, then the overall average speed is the average of these two: 60 mph.

However, this is wrong. The intutive reason is that when the lap is completed with a higher average speed, the lap took less time to complete and so contributes to the average less.

Let us be explicit. Suppose that each lap is of distance D. Let us say that the first lap was completed with an average speed of v1, which took time t1. Likewise, let us say the second lap was completed with an average speed of v2, which took time t2.

Straight away we have the following relationships:

v_1 = \frac{D}{t_1}\qquad v_2 = \frac{D}{t_2}

Let us call the overall average speed u. Then u is:

u = \frac{\mbox{Overall distance}}{\mbox{Overall time}} = \frac{2D}{t_1+t_2} = \frac{2D}{\left(\frac{D}{v_1} + \frac{D}{v_2}\right)} = \frac{2v_1 v_2}{v_1 + v_2}

Suppose, as in the question, that our first lap was at 30 mph. We therefore have that u = \frac{60 \times v_2}{30 + v_2}. Suppose we wish u = 60. Then we have that 1 = \frac{v_2}{30+v_2}. Note that there is no value of v2 that makes this true!

Therefore the cyclist has blown his chance! He cannot possibly beat the world record!

Another way to see the conclusion is as follows. The world record time is distance/avg. speed = 2D/60 = D/30. The first lap was took a time of distance/avg. speed = D/30. Therefore all the time is taken, and we reach the same conclusion as before.

Given the lack of sophistication in the previous questions, it seemed this was not the answer they were looking for. It is certainly a lot harder than the others, especially given how it is a trick question! I thought it safer just to give the naïve answer, especially considering that it might be considered suspicious if the person I was doing it on the behalf of got it right.

Expected number of different birthdays

Suppose there are n people in a room. It is the well known ‘birthday problem‘ that if n > 22 the probability of two people sharing the same birthday is greater than 50%, and so it is very likely that there aren’t n unique birthdays. However, what is the expected number of unique birthdays?

[Let us assume there are D days in a year, in order to be more general.]

Actually, the expected number of unique birthdays is very easy to calculate. Let e(n) denote the expected number of unique birthdays when there are n people.

Choose one of the n people. Then either they have a different birthday than everybody else, or they don’t. They have a different birthday than the other n-1 with probability \left(\frac{D-1}{D}\right)^{n-1}. Let us write \phi for (\frac{D-1}{D}), and so the probability that they have a different birthday to everybody else is \phi^{n-1}. In this case, the expected number of unique birthdays is 1+e(n-1). In the other case, which thus has probability  1 - \phi^{n-1}, the expected number is just e(n-1).

Hence,

 e(n) = \phi^{n-1}(1+e(n-1)) + (1-\phi^{n-1})e(n-1) = \phi^{n-1} + e(n-1)

As e(1) = 1, it follows that:

e(n) = \phi^{n-1} + \phi^{n-2} + ... + \phi + 1 = (\phi^n - 1)/(\phi-1) = D(1-\phi^n)

 (As one should expect, as n tends to infinity this tends to D, as it is almost certain that every birthday gets taken)

For instance, with D = 365, you should expect about 21 different birthdays when there are 22 people, or 46 different birthdays when there are 50 people. When there are 1000 people, there will be around 341 different birthdays. Perhaps it is quite surprising that you should expect there to be so many (24) unclaimed birthdays with so many people!

Consider the following problem:

Suppose a factory is in a country with the following law: Every worker must work every day, unless it is the birthday of one of the workers. In this case, everybody has the day off. How many people should you hire in order to maximize the expected number of man-days worked every year?

Naturally, if there is only a single person he will certainly work 364 days (D-1) a year. If there are two, they are likely to have different birthdays and so each will work 363 days a year (D-2), giving a total of 726 days.

The expected number of man days worked will be the number of people, n, multiplied by the expected number of non-birthdays. The number of non-birthdays is just D – e(n). Thus we are trying to maximise the following:

W(n) = n(D-e(n)) = nD\phi^n

Considering n as a real number instead of an integer, one can find that the function W has a maximum at n = -1/\log\phi = -1/\log(1-1/D) \approx D - 0.5. Thus the maximum must be around this, and so for all but the smallest D (where the approximation is not valid), the maximum will be either D-1 or D.

In fact, it is easily seen that W(D) = W(D-1). It follows that one should employee either D or D-1 people. Since you will probably have to pay these workers, it is better to go for the D-1 people.

A simple change of this problem is to consider that for each man-day of work in the factory, you earn £a. However, you must pay each worker £y per year. Then instead you are maximising the yearly income of:

V(n) =anD\phi^n - ny

The derivative of this is V'(n) = aD\phi^n + a D n \phi^n \log \phi - y. Hence if V'(n) = 0 we must have:

y/aD = \phi^n(1+n \log \phi) = e^{n \log \phi} ( 1 + n \log\phi )

Define w = 1 + n\log\phi so that:

y/aD = w e^{w-1}

And so we have that:

ey/aD = w e^{w}

Let us note that y/aD is the ratio between what you pay the worker per year, and what he earns for you per year if he were to work every day. Let us call this ratio P.

Note that when z is positive, the equation z = w e^w always has a unique solution. The function which takes z to w is called the ‘Lambert W Function‘. Hence we have that:

W(eP) = W(ey/aD) = w = 1 + n\log\phi

It follows that:

n = (W(eP)-1)/\log\phi

As P will be small, and in particular less than 1, an approximation of the Lambert W function may be useful. We will use the Taylor Series approximation W(x) \approx x-x^2+3x^3/2 - 8x^4/3. Along with the usual log approximation, this gives:

n \approx D-\frac{e y}{a}+\frac{e^2 y^2}{a^2 D}-\frac{3 e^3 y^3}{2 a^3 D^2}+\frac{8 e^4 y^4}{3 a^4 D^3}

Or, in terms of P,

n \approx \frac{1}{6} D \left(6-6 e P+6 e^2 P^2-9 e^3 P^3+16 e^4 P^4\right)

For instance, suppose that I pay my workers £18,000 per year. They generate about £350 in profit for me each day they work. They work every day, except for when one of them has a birthday. By evaluating the W function exactly, I find out that the maximum expected profit is when there are around 260 workers. The approximation yields 269 workers. If the profit they generate per day were to be decreased to £75 then the approximation is completely inaccurate. Whilst I should only employee 72 people, the approximation gives over 7,000!

Three Birthdays On The Same Day

At the company I work at, which has about 35 members of staff, it was discovered that three people have the same birthday. The so-called ‘Birthday Paradox‘ tells us that two people having a birthday on the same day is much more likely than one would imagine, so it is interesting to calculate the probability that three people have the same birthday.

Let us suppose that there are N members of staff. Let our probability space be the set of N-tuples of integers between 1 and 365 (inclusive). There are 365^N elements in this probability space.

Let us denote the event that there is at least one triplet B. Similarly, let us denote the event that there are exactly k pairs of people who are sharing a birthday (and no triplets or higher) as A_k.

Then we have that the probability that B happens is one minus the probability that A_0 or A_1 or A_2, \ldots happens. That is,

\mathbb{P}(B) = 1 - \mathbb{P}(A_0) - \mathbb{P}(A_1) - \mathbb{P}(A_2) - \ldots

Hence we must find an expression for A_k – the probability that k pairs of people have the same birthday and everybody else has a different one.

Recall that we are working in the space of ordered N-tuples. Therefore we need to select the positions of each of the pairs. For the first pair we do “N choose 2”, for the second we do “(N-2) choose 2”, and so forth. So, selecting the positions of the birthdays we want to be duplicated, we can do:

\binom{N}{2} \binom{N-2}{2} \cdots \binom{N-2(k-1)}{2}

Note that we have an ordered list of k unordered pairs.

We can simplify the above expression to \frac{N!}{2^k (N-2k)!}.

Now, we need to choose the k birthdays for these pairs to have as the common day. Obviously, each pair must be different, else we’d have (at least) four people with the same birthday, and we don’t want more than two people with birthdays on the same day.

Suppose we pick the k days in an ordered fashion (i.e. 365\times364\times\cdots\times(365-k+1)). Then we will have over-counted, because the pairs are in an ordered list. For instance, suppose we picked the ordered list of unordered pairs “Person 1 & Person 2”, “Person 3 & Person 4”. Then we selected the ordered list of birthdays “1st Jan, 2nd Jan”. Then this would give us the same thing as if we’d selected the pairs “Person 3 & Person 4”, “Person 1 & Person 2” with the list of birthdays “2nd Jan, 1st Jan”. In this case we over counted by a factor of 2. In general, we will overcount by the number of permutations of the list of pairs. This is k!.

Now, the remaining N-2k people can have any remaining birthday. So the first has a choice of 365-k, the next a choice of 365-k-1 and so forth. Therefore,

|A_k| = \frac{N!}{2^k (N-2k)!}\frac{( 365 \times \cdots (365-n+k+1))}{k!}

So, for instance, in Mathematica:

A[N_, k_] := N!/(2^k (N - 2 k)!) * 365!/((365 - (N - k))!*k!)

We can verify this by ensuring that 1 - \mathbb{P}(A_0) is the probability that at least two people will share a birthday in a group of N people. Remember that \mathbb{P}(A_k) = |A_k|/365^N.

We wish to find the sum of the A_i. There is no obvious closed form expression for it, so it will suffice to numerically calculate it for the desired values. Doing so yields the following graph:

The probability of three birthdays on the same day in a group of various sizes.

In particular, for my situation – that out of a company of 35 people, three had the same birthday – has a probability of about 4.5%. In fact, these members were at the company back when it was only 12 people strong, and then it had a probability of only 0.33%.

You need a group of 87 people before the chance of three people having a birthday on the same day is 50%. 75% happens after 110 people and 25% at 65 people.

The following graph shows the probability of having two people sharing a birthday in blue and three people sharing a birthday in red:

The red is the probability of three people (or more) sharing a birthday. The blue is the probability of two people (or more) sharing a birthday. The horizontal axis is the number of people; vertical is the probability.

This spreadsheet gives the full table the probabilities. (Apologies for the Excel format, WordPress didn’t seem to want plaintext files uploaded.)

The Coin Problem

Here is a problem: You have 10 coins. One of these coins is heavier than the others, but they are all otherwise identical. You have a balance scale which you can use to compare the weights of any two sets of coins. You must devise a strategy to find the heavier coin in the minimum number of weighs (in the worst case).

The solution is simple. Split into two groups of 5 and compare those two. Select the heavier of the two sets and compare two sets of two in there. If they are equal, it must’ve been the one you didn’t compare. If they are not, you compare the two on the heavier side to finally find the heaviest. So it takes only 3 weighs.

Now, what if the odd coin out is either heavier than the others or lighter than the others but you don’t know which? In fact, it is still possible to do it in three goes. The following diagram shows you how.

 

 

The ten coins are labelled as shown at the top. ‘A’ is short for A1 + A2 + A3, and similarly for ‘B’ and ‘C’. The underlines denote that the coin is a known reference (i.e. known to be neither heavier nor lighter). If A and B are not the same weight, we assume A is heavier (as otherwise you can just relabel them).

Note that in every path except for the first, which ends in D, you know not just which coin it is, but if the coin is heavier or lighter than the others.

%d bloggers like this: