Pecking order of pigeons?

I was going though problems on graph theory posted by Prof. Ericksson from my alma-mater and came across this rather unique question about pigeons and their innate tendency to form pecking orders. The question goes as follows:

Whenever groups of pigeons gather, they instinctively establish a pecking order. For any pair of pigeons, one pigeon always pecks the other, driving it away from food or potential mates. The same pair of pigeons always chooses the same pecking order, even after years of separation, no matter what other pigeons are around. Surprisingly, the overall pecking order can contain cycles—for example, pigeon A pecks pigeon B, which pecks pigeon C, which pecks pigeon A.

Prove that any finite set of pigeons can be arranged in a row from left to right so that eve开发者_C百科ry pigeon pecks the pigeon immediately to its left.

Since this is a question on Graph theory, the first things that crossed my mind that is this just asking for a topological sort of a graphs of relationships(relationships being the pecking order). What made this a little more complex was the fact that there can be cyclic relationships between the pigeons. If we have a cyclic dependency as follows:

A->B->C->A

where A pecks on B,B pecks on C and C goes back and pecks on A

If we represent it in the way suggested by the problem, we have something as follows: C B A

But the above given row ordering does not factor in the pecking order between C and A.

I had another idea of solving it by mathematical induction where the base case is for two pigeons arranged according to their pecking order, assuming the pecking order arrangement is valid for n pigeons and then proving it to be true for n+1 pigeons.

I am not sure if I am going down the wrong track here. Some insights into how I should be analyzing this problem will be helpful.

Thanks

I would prove that using induction indeed (a>b means a peacks b):

1. for k=2 it obviously holds
2. let for k=n there's always required order, lets prove that it exists for n+1. Choose and order any n pigeons (A1>A2...>An) from given n+1. And let C is a (n+1)th pigeon.
   If C pecks A1 then it can be added to the start of the "line" and statement proved. If A1 pecks C then lets compare C with A2 - if C pecks A2 then it can be inserted between A1 and A2 and statement holds. If not - repeat that comparing process till last pair - A(n-1) and An, as process goes we assume that A(n-1) > C. If C>An then C can be inserted between A(n-1) and An, if not - it can be inserted to the end of the "line".

qed

P.S. Note that "pecking cycles" do not necessarily exist - if we assign pigeons number from 1 to n and assume that pigeon pecks another if his number is greater then we obviously can order them in line but not in circle so that each pigeon pecks his left neighbour.

P.P.S. That proof also gives an algorithm to construct the required order.

Have you considered constructing a directed graph then looking for a Hamiltonian Path that visits every point (pigeon) once? The Hamiltonian path should reveal the sequence - this isn't a proof, though. Just a solution.