3
$\begingroup$

Five cars are driving in a roundabout traffic at the same moment. Each comes from an other direction, and drives less than one full round. Also each car leave the roundabout traffic in an other direction than the other. The cars are forbidden to pass cars in the roundabout traffic. They can leave the roundabout whenever they want, but they drive less than one full round, and in the end all cars are driving in differnt directions.

Question:

How many possible combinations are there for the cars to leave the roundabout ? Give a proof.

enter image description here

$\endgroup$
6
$\begingroup$

The question simply (simply? yes; see the end for comments on one issue that's been raised) asks

how many permutations of five things there are with no fixed points; that is, nothing ending up in the same place as it began.

There is a famous answer to this

for an arbitrary number of things; with $n$, the answer is $n!\left(\frac1{0!}-\frac1{1!}+\frac1{2!}-\cdots\pm\frac1{n!}\right)$, which is approximately $n!/e$. For $n=5$ this becomes $120\left(\frac1{1}-\frac1{1}+\frac12-\frac16+\frac1{24}-\frac1{120}\right)=120-120+60-20+5-1=44$.

It can be proved

using the so-called inclusion-exclusion principle. For $S$ any subset of the things being permuted, let $A_S$ be all the permutations for which everything in $S$ is a fixed point; then $|A_S|=(n-|S|)!$. We want to know how many things are in no $A_S$ other than $A_{\emptyset}$. Begin by taking $A_\emptyset$ itself; then remove all the $A_S$ with $|S|=1$; now we have removed the permutations with fixed points but gone too far by removing ones with two fixed points twice, so add back the $A_S$ with $|S|=2$; now, alas, any permutation with three fixed points has been removed three times and added three times, so take those out by removing all the $A_S$ with $|S|=3$; continuing in this way we get $|A_\emptyset|-\sum_{|S|=1}|A_S|+\sum_{|S|=2}|A_S|-\cdots$. Term $k$ of this is $(-1)^k$ times the sum of $\binom{n}{k}$ things each equal to $(n-k)!$. Adding the whole thing up we get exactly the series I described.

If

the reasoning leading to $|A_\emptyset|-\sum_{|S|=1}|A_S|+\sum_{|S|=2}|A_S|-\cdots$ seems a little handwavy, there is a more rigorous way to express it in terms of the binomial expansion of $(1-1)^n$, which you will readily find by putting "inclusion-exclusion principle" into your favourite search engine.

Now, what about that restriction on passing?

It doesn't make any difference. Pick any derangement. Imagine that all the cars enter the roundabout together, go around in the same direction, and leave when they reach their "target" exit. Nothing in this requires that their paths cross. If exiting the roundabout is quick enough, the car behind needn't even slow down :-).

$\endgroup$
  • $\begingroup$ You may have to show the formula actually works, since the cars each drive less than once around and presumably the roundabout has only one lane so cars cannot pass each other. $\endgroup$ – RShields Jun 21 at 21:22
  • $\begingroup$ If the cars are forbidden to pass one another then the answer will be different and smaller. @Matti, would you like to clarify? $\endgroup$ – Gareth McCaughan Jun 21 at 21:23
  • $\begingroup$ The answer may not be smaller. It seems like cars can exit at any time and can "pass" exited cars. Perhaps there's a way to show that cars can't block each other, therefore any rot13(qrenatrzrag) can occur. $\endgroup$ – RShields Jun 21 at 21:28
  • $\begingroup$ Sorry ! I forgot to mention it. The cars are forbidden to pass other cars in the roundabout traffic. $\endgroup$ – Matti Jun 21 at 21:28
  • 1
    $\begingroup$ Actually, unless I'm confused it's not a problem. I've added some comments on the issue to my answer. $\endgroup$ – Gareth McCaughan Jun 22 at 1:20
4
$\begingroup$

The answer should be

44, the number of derangements, or permutations with no fixed points, on five elements.

because

no car needs to pass any other if they all arrive at the same time; you can treat the cars' movements as discrete, moving one exit each step, and each car will indeed reach its destination in at most 4 steps without blocking any other cars.

$\endgroup$
  • $\begingroup$ Note that each car takes less than 1 circle and presumably they block each other off, so not every rot13(qrenatrzrag) is necessarily possible. $\endgroup$ – RShields Jun 21 at 21:19
  • $\begingroup$ So the cars aren't arriving at the same time? $\endgroup$ – AxiomaticSystem Jun 21 at 21:26
  • $\begingroup$ They do arrive at the same time, probably don't exit at the same time, but you'll want to provide reasoning for why no car needs to pass another or make more than one round. $\endgroup$ – RShields Jun 21 at 21:31
  • $\begingroup$ If they all go turn onto the roundabout together, and go around at the same speed, why would they need to overtake? $\endgroup$ – Jaap Scherphuis Jun 21 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.