Pecking order of pigeons?
- by sc_ray
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 every 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
