# Fleas Problem

Discussion in 'Mathematics' started by andy b, Mar 23, 2012.

1. hello,

i'm having trouble getting into a problem. i want to do more 'peopls maths' of this style but i'm also short of time so wondering if anybody can help out. the problem (from mike ollerton's 'getting the *** to add up') is:

a number of students in a line are to change their position from sitting down to all standing up, according to the conditions ...

1. only one flea can make a move at one time.
2. a move is defined as a flea either standing up or sitting down.
3. in order for a flea to make a move the flea to their immediate left must be sitting down and anyone else further to their left must be standing up.
4. the flea from the far left (from the viewpoint of the other fleas) can move at any time.

so with five fleas A, B, C, D, E, sitting down, the first move could be for flea D or E to stand up.

the problem is to minimise the number of moves required to get everyone standing up, and to generalise for any number of fleas.

mike ollerton writes that the general solution makes use of A-level type knowledge.

can anyone help?

thanks.

- andy

2. This is actually a well established problem, and one I encountered on my travels around China:
http://en.wikipedia.org/wiki/Chinese_rings_puzzle
I spent much of the flight home thinking about the general formula! It can be solved as a recurrence relation. Suppose we define f(n) to be the number of moves required to get the first n people from the left standing up. Then we can perform the following sequence of moves:
1. Get all but the nth and (n-1)th people to stand up. This costs f(n-2) moves according to our definition.
2. Since for the nth person, the person to his left is sitting down, and the n-2 people left of that standing up, this person can now stand up. This costs 1 move obviously.
3. We now have to move the leftmost n-2 back down again. Once this is done, we've got the nth person standing up and all people to the left of them sitting down. We can therefore now solve the problem for f(n-1) people.
So the recurrence relation is:
f(n) = f(n-1) + 2 f(n-2) + 1
And the base case: f(1) = 1 (as the left-most person is free to stand-up/sit-down).
Solving, we have:
So for 5 fleas, that's 21 moves.

3. Incidentally, the same kind of strategy can be applied to the much more popular 'Towers of Hanoi' game: http://en.wikipedia.org/wiki/Towers_of_Hanoi . This Wikipedia article has a ton of pretty awesome maths.
To get n disks from the starting pole to the target pole. We recursively move the top n-1 discs to an intermediate pole, move the largest disc to the target pole, then again recursively move the n-1 other discs from the intermediate pole to the target one.
That's:
f(n) = 2f(n-1) + 1.
f(1) = 1
Solution in this case is a much simpler f(n) = (2^n) - 1.

4. i see how you got this ---> f(n) = f(n-1) + 2 f(n-2) + 1

but how did you get from that to this ----> f( n ) = (-1)^(n+1)/6 + 1/3 2^(n+1) - 1/2

thanks!

5. I would have to talk about homogenous/inhomogenous/auxiliary equations. It's not in any A Level syllabuses as far as I know. I recommend Googling 'solving recurrence relations'. 6. the book does specifically say that the problem makes use of A-level knowledge, so i wonder if there's another way to get a solution.

7. Glad to be of help.
I'm pretty certain recurrence relation sequences like this (including for example the Fibonacci Sequence - the classic f(n) = f(n-1) + f(n-2)) can't be solved without this kind of technique. So I'd tentatively hazard a guess that this Mike guy is wrong. But others may wish to correct me...

8. Similar to the Fibonacci and Lucas sequences then?
Oops repeating the previous posts then, sorry folks.

9. In the case of f(n) = f(n-1)+2f(n-2) + 1, we can first get rid of the constant by setting g(n) = f(n)+1/2, so our equation becomes g(n) = g(n-1) + 2g(n-2).

Next, writing h(n) = g(n) + g(n-1), we get

h(n) = g(n) + g(n-1) = g(n-1) + 2g(n-2)+g(n-1) = 2(g(n-1)+g(n-2) = 2h(n-1).

We can then successively solve for h, g and f.

*Technically*, this doesn't require anything beyond A-level maths, but in practice it's not something you'd expect someone who's only done A-level maths to come up with.