## Look at that S Car Go

Posted by Karl Sharman on July 16, 2014 – 1:19 am

Not many of you will be aware of my proud collection of racing snails. I have 8 of the speedy little critters. So fast are they, that I have an elaborate camera set up for those inevitable photo finishes.

Bonus point for identifying the title quote!

In how many ways, counting ties, can my 8 Racing Snails cross the finishing line? (For example, A and B, can finish in three ways: A wins, B wins, A and B tie.)

July 16th, 2014 at 3:41 am

S Car Go – Escargot! Stop it, you’re killing me!

If all eight snails tie, that is 1 outcome.

If seven tie the other can be first or last: 2 outcomes

If six tie we have 6 arrangements of 1, 2 and 6T: 3! outcomes.

Likewise five tie: 4! outcomes, four tie: 5! outcomes, three tie: 6! outcomes, two tie: 7! outcomes. That leaves 8! outcomes where there are no ties.

So 1! + 2! + 3! + 4! + 5! + 6! + 7! + 8! = 46,233 if I’m not mistaken (which I usually am).

July 16th, 2014 at 4:17 am

Hi Wiz. I expect you got the bonus points. But there are over 160,000 ways to finish (if, in turn, I’ve not goofed).

July 16th, 2014 at 4:37 am

Hi Chris,

You’re absolutely right as usual.

So, for example, where I said “If seven tie the other can be first or last” I should have realised that the “other” could be any one of 8 snails. So score 16, not 2, for this category.

It’s bedtime here in Oz so I’ll leave it there for now. I’m sure others will have a better answer before another day dawns here.

July 16th, 2014 at 6:46 am

Brute force gives me 518745. Of course, the probability of an arithmetic error throughout the computations is quite high. I’ll try to come up with a more elegant solution…

July 16th, 2014 at 8:34 am

I’ve just got it to 526375. My head is spinning.

As part of my “strategy” I’ve used the 22 partitions of 8. In the past when I’ve invoked partitions, I’ve found that it wasn’t necessary and that a neater solution was available.

July 16th, 2014 at 8:50 am

Correction (I’d made a silly mistake): 526305

That looks a bit like your number Slavy. Is your 7 a typo or similar?

July 16th, 2014 at 8:54 am

Another silly. Now I’ve got 545835

Jeez, this is a major pain. Getting my head straight was one thing, but screwing up the mechanical calculations is so easy to do.

July 16th, 2014 at 10:37 am

In desperation I’ve done some Googling. In consequence, I’m sticking with 545835 (that calls for a definite phew!). As I suspected, one doesn’t need to explicitly deal with partitions. There is even a simple, but infinite, summation that does it. Sum(m = 0 to ∞, m^8 / 2^m) / 2

See http://en.wikipedia.org/wiki/Ordered_Bell_number for more info, including a finite sum formula.

July 16th, 2014 at 10:43 am

Been there, done that My formula is:

7!*15 + C(7,2)*6!*13 + (C(7,3)+C(7,2)*C(5,2)/2!)*5!*11 + (C(7,4)+C(7,3)*C(4,2))*4!*9 + (C(7,5)+C(7,3)*C(4,3)/2!+C(7,2)*C(5,2)*C(3,2)/3!)*3!*7 + (C(7,6)+C(7,5)*C(2,2)+C(7,4)*C(3,3))*2!*5 +C(7,7)*1!*3

The computations are a lot, so, as I said, most probably my answer is wrong. However, I expect the formula to be correct, unless I goofed again…

July 16th, 2014 at 10:56 am

We can partition the 8 snails into the following 22 distinct sets by size alone:

8, 7+1, 6+2, 6+1+1, 5+3, 5+2+1, 5+1+1+1,

4+4, 4+3+1, 4+2+2, 4+2+1+1, 4+1+1+1+1,

3+3+2, 3+3+1+1, 3+2+2, 3+2+1+1+1, 3+1+1+1+1+1

2+2+2+2, 2+2+2+1+1, 2+2+1+1+1+1, 2+1+1+1+1+1+1,

1+1+1+1+1+1+1+1

For each of those, we have to calculate the number of ways we could choose them: e.g. for 5+3+1, there are 8!/(5! 3! 1!) = 56. Further, each of those sets can finish in 3! different orders i.e. 5,3,1; 5,1,3; 3,5,1; 3,1,5; 1,3,5; 1,5,3

For 4+2+2, there are 8!/(4! 2! 2!) = 420 ways of picking the groups. However, for each of those there are 3!/(1! 2!) different orders they could be in i.e. 4,2,2; 2,4,2; 2,2,4.

Although the C(n,r) type formulae are usually used, a neater sibling, known as the multinomial function by Wolfram is preferred by me. I’ll use M(…) to denote that function. M(a,b,c,…) = (a+b+c+…)!/(a! b! c! …).

The total number of races with the 5+3+1 set is M(1,1,1) M(5,3,1) and for the 4+2+2 set it’s M(1,2) M(4,2,2). The first factor is the list of the count of how many items there are of each size. So 5+3+1 has 1 each of size 5,3 and 1. The 4,2,2 set has 1 of size 4 and 2 of size 2.

Doing this for all 22 partitions and adding the results gives 545835 different races.

Considering that there are only 8 snails, I think that’s quite amazing.

July 16th, 2014 at 11:03 am

ok, in the formula I’ve missed the term C(7,4)*C(3,2)*3!*7 which should add 4410 to the answer…

July 16th, 2014 at 11:04 am

Hi Slavy. Your formula does give 518745. I haven’t worked out the pattern in it, so can’t say if there is a typo or some such. But the result is so close to the correct one, I have to assume that your basic idea must be good.

July 16th, 2014 at 12:11 pm

Hi Slavy. Posts crossing. Including the missing term takes the result to 523155.

July 16th, 2014 at 1:38 pm

To eliminate any ambiguity, here’s the full calc:

M(1)M(8) + M(1,1)M(7,1) + M(1,1)M(6,2) + M(1,2)M(6,1,1) + M(1,1)M(5,3)

+ M(1,1,1)M(5,2,1) + M(1,3)M(5,1,1,1) + M(2)M(4,4) + M(1,1,1)M(4,3,1)

+ M(1,2)M(4,2,2) + M(1,1,2)M(4,2,1,1) + M(1,4)M(4,1,1,1,1)

+ M(2,1)M(3,3,2) + M(2,2)M(3,3,1,1) + M(1,2,1)M(3,2,2,1)

+ M(1,1,3)M(3,2,1,1,1) + M(1,5)M(3,1,1,1,1,1) + M(4) M(2,2,2,2)

+ M(3,2)M(2,2,2,1,1) + M(2,4)M(2,2,1,1,1,1) + M(1,6) M(2,1,1,1,1,1,1)

+ M(8)M(1,1,1,1,1,1,1,1)

M(a,b,c,…) = (a+b+c+…)! / (a! b! c! …) NB M(n) = 1

July 17th, 2014 at 4:05 am

I started with only a couple of snails, and then expanded to a systematic way of counting the possible outcomes.

Four snails may finish in 1, 2, 3, or 4 blocks. Labeling the snails a, b, c, d, one example of three blocks is: (a) (b) (c, d). This means that snails c and d have tied, and that snails a, b, and (c, d) have finished separately.

Note further that the three blocks — (a), (b), (c, d) — may be arranged in 3! = 6 ways. Clearly this is true of any partition that consists of three blocks.

For each number of blocks, the possible partitions and their number, the number of arrangements per partition, and the number of outcomes:

No. blocks – Partitions – No. partitions – Arrangements per partition – Outcomes

1 – (a, b, c, d) – 1 – 1! – 1

2 – (a) (b, c, d), (b) (a, c, d), (c) (a, b, d), (d) (a, b, c), (a, b) (c, d), (a, c) (b, d), (a, d) (b, c) 7 – 2! – 14

3 – (a) (b) (c, d), (a) (c) (b, d), (a) (d) (b, c), (b) (c) (a, d), (b) (d) (a, c), (c) (d) (a, b) – 6 – 3! – 36

4 – (a) (b) (c) (d) – 1 – 4! – 24

Hence, counting ties, four snails can cross the finishing line in 1 + 14 + 36 + 24 = 75 days, oops, I mean ways.

When another snail joins the race we need a way to easily calculate the number of ways n snails can cross the finishing line in k blocks – a recurrence relation.

Let S(n, k) denote the number of ways n snails can cross the finishing line in k blocks. If another snail joins the race, there are now have n + 1 snails that finish in k blocks. Then there are two mutually exclusive cases, which encompass all possibilities:

• The extra snail is alone in a block; i.e., it does not tie with any other snails. Then the other n snails must comprise k − 1 blocks. This can be done in S(n, k − 1) ways.

• The extra snail is in one of the k blocks. For each block, this may be done in S(n, k) ways.

We conclude that, for n > k, S(n + 1, k) = S(n, k − 1) + kS(n, k).

Using this recurrence relation, together with the initial conditions, S(n, 1) = S(n, n) = 1, we can determine S(8, 1), S(8, 2), …, S(8, 8). Letting H8 denote the number of ways 8 snails can cross the finishing line, we obtain:

1×1! + 127×2! + 966×3! + 1701×4! + 1050×5! + 266×6! + 28×7! + 1×8! = 545835.

Therefore, counting ties, eight snails can cross the finishing line in 545835 ways.

The 7 losers – I ate with garlic butter, the winner went on to stud. Survival of the fastest. I recommend a nice, chilled Sancerre.

S car go (Escargot)- Eddie Murphy in Trading Places.

July 17th, 2014 at 7:05 am

Most probably I missed some cases – I wanted to generalize the problem so I was trying to involve induction – this is why my formula looks differently. It’s from the perspective that we add the 8th snake to the other 7. If none of the first 7 seven snakes tie, then there are 15 possibilities for the eight one – it can finish 1st, 2nd, …, 8th alone or tie with one of the other 7 snakes. If two snakes already tied – we can think of them as 1 super-snake and there are 13 possibilities for the eight one (same argument). And so on… Anyway, I don’t think there is a close formula for n snakes, so my approach is clumsier than the direct one of Chris and Karl.