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/

]]>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.

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.

]]>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.

]]>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?

]]>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
from math import factorial def sumdigits(n): r = 0 while n: r, n = r + n % 10, n / 10 return r def nomatch(n): # number of permutations with no fixed points s = 0 for i in xrange(n + 1): s+= (-1) ** i * factorial(n) / factorial(i) return s for n in xrange(3, 100): allmove = nomatch(n) somesame = factorial(n) - allmove if sumdigits(allmove) == sumdigits(somesame): print n, allmove, somesame |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
from itertools import count # a permutation of a set of items numbered 1 to n in which no item is # in its 'natural' position is called a derangement. The number of # derangements of n items is given by the recurrence relation: # # d[n] = n * d[n - 1] + (-1) ** n # # with d[1] = 0 and d[2] = 1 # d is the number of derangements of n cows, fac is the number of # pemutations of n cows. dd, d, fac = 0, 1, 2 for n in count(3): # calculate the number of derangements and permutations dd, d, fac = d, n * d + (-1 if n % 2 else 1), n * fac # The number of permutations with at least one cow in a booth # with a matching number is fac[n] - d[n] if sum(int(x) for x in str(d)) == sum(int(x) for x in str(fac - d)): print('The herd has', n, 'cows.') break |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# a permutation of a set of items numbered 1 to n in which no item is # in its 'natural' position is called a derangement. The number of # derangements for n items is the nearest integer to (n! / e). f, e = 2, 2.718281828459045 for cows in count(3): f *= n d = round(f / e) # The number of permutations with at least one cow in a booth # with a matching number is n! - d[n] if sum(int(x) for x in str(d)) == sum(int(x) for x in str(f - d)): print('The herd has', n, 'cows.') break |

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\).

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.

]]>