# Sunday Times Teaser 2665 – Milky Ways

### by H Bradley and C Higgins

A farmer who has cows ear tagged 1, 2, 3, …,  milks them in individual booths also numbered 1, 2, 3, …   The cows choose booths randomly.

The farmer has noticed during milking that frequently no cow is in a booth with a number that matches their own.

So he has worked out the number of different ways this can  happen.  He has also worked out how many different arrangements there are in which one or more cows are in booths with matching numbers.

The two answers are both less than one million and the sums of their digits are the same.

How many cows are in the herd?

Here is an alternative using a different expression for the number of derangements of n items (Arthur uses yet one more below).

However, although ths version works for the teaser, it soon fails for larger solutions because the factorial soon reaches the upper limit of numbers set by the use of floating point arithmetic. To avoid this it would be necessary to use rational fractions in place of floating point and to have an extended precision value for $$e$$.

### Derangements

Here is a derivation of a recurrence relation for the number of derangements $$d_n$$ of $$n$$ items.

Consider a situation in which we have $$n$$ items in an existing arrangement and we then add item $$(n + 1)$$ on the end. If we started with a derangement this will destroy it, but we can easily recover it swapping our new item with any of the $$n$$ items in the pre-existing derangement. And, since we can do this for each of the $$d_n$$ derangements of $$n$$ items, we end up with $$n d_n$$ new derangements.

But there is one other case in which we can make further derangements. If exactly and only one item is correctly positioned in the original arrangement, we can then swap the new item with this item and form a derangement. And, since the correctly positioned item can be any of the $$n$$ items with the remaining $$(n-1)$$ items deranged, this gives a further $$n d_{n?1}$$ derangements.

So adding these two cases gives the recurrence relation:$d_{n+1}=n(d_{n}+d_{n?1})$ with $$d_1=0$$ and $$d_2=1$$. Going further, this can be rewritten as: $d_{n+1}-(n+1)d_n=-(d_n-nd_{n-1})$ where the right hand side is of the same form as the left hand side with $$(n+1)$$ replaced by $$n$$. So, by repeatedly substituting for the expression on the right, we can show that: $d_{n+1}-(n+1)d_n=(-1)^{n-1}(d_2 – 2d_1)$ and finally (with $$n+1\rightarrow n$$): $d_n=nd_{n-1}+(-1)^n$ which provides an alternative recurrence relation. This recurrence relation can be solved analytically to show that: $d_n=\frac{\Gamma(n+1,-1)}{e}=\left[\frac{n!}{e}\right]$ where $$\Gamma(z,a)$$ is the Incomplete Gamma Function and $$\large[x]$$ is the nearest integer function.

Hi Brian

When I had found d[n] for n up to 5 and failed to find a closed formula I turned to the web and found the recurrence relation (which I cannot prove to be correct) and the interesting solution
d[n] = nearest integer to{ n ! /e }. I also found a list of values of d[n].

After this “cheating” there was not much more to do. I wonder whether there are any larger solutions – could your program be adapted to investigate?

Yes, its easy to find larger solutions – here are the next two of many (with the total number of permutations (n!) and the number of derangements (!n)):

The herd has 46 cows.
(n! =) 5502622159812088949850305428800254892961651752960000000000
(!n =) 2024301565129266265854367142632387886092660697797387753785

The herd has 52 cows.
(n! =) 80658175170943878571660636856403766975289505440883277824000000000000
(!n =) 29672484407795138298279444403649511427278111361911893663894333196201

and then 94, 115, 124, 274, 313, 346, 415, 616, 889, 940, 973, 1069, 1192, 1408,
1591, 1687, 2182 … (the last with a 517 digit number of pemutations).

I had to look up the formula for the number of derangements as well since doing by counting derangements was easy but less less satisfying for me than a mathematical solution.

• The question setter was careful to stipulate that the cows are numbered 1,2,3,…, implying that there are at least 3 cows, as otherwise there would be a solution with 2 cows.

The next solution is 94 cows:
 40001965405962165157332356557172764050060243209964 53141510786154605328497272578932957164703433966888 4239468369562286934734488981651139921638228569 
perms with no ow in its own stall and
 68734650259712142870032928699613836954126560370218 34089238951288799191489669213830065746218024374657 4321397281640098405796199018348860078361771431 
perms with at least one cow in its own stall.

?f (n!) is the number of arrangements of (n) items in (n) places, out of which (d(n)) is the number of arrangements in which no items are in their natural places, we obtain (d(n)=n d(n-1)+(-1)^n) and the number of arrangements (m(n)) in which one or more items are in their natural position (m(n)=n!-d(n)).

Hence here we have [begin{array} dd(1)=0,&m(1)= 1 \ d(2)=1,&m(2)=1 \ d(3)=2,&m(3)=4 \ d(4)=9,&m(4)=15 \ d(5)=44,&m(5)=76 \ d(6)=265,&m(6)=455 \ d(7)=1854, &m(7)=3186 \ d(8)=14833,&m(8)=25487 \ d(9)=133496,&m(9)=229384end{array}]

One can reach the answer very easily from here.

I did A level maths, obtained an A grade, yet I found this very testing ( without a computer). Could you use elementary probability instead of derangements ? Thanks.

Hello Dave,

Welcome to the site. Since the problem is about derangements, it will be hard to avoid them. But you can deal with them without going beyond A-level maths and I have now expanded my main comment above to cover this. I didn’t use any maths beyond A level so it should allow you to find a solution maanually.

However, of course, this site is intended for those who wish to discuss and present solutions using Python. The relevant site for the discussion of manual solutions is: https://sites.google.com/site/sundaytimesteasers/