The procedure for hardening pigeons?

Question

I walked, although the problems in graph theory published by Prof, Ericksson from my alma-mater , came across this rather unique question about pigeons and their innate tendency to form hierarchical orders. The question is:

When groups of pigeons gather, they instinctively place an order. For any pair of pigeons, one pigeon always pecks another; driving is far from food or potential mates. The same pair of pigeons always selects the same hierarchy order, even after several years of separation, regardless of what other pigeons are around. Surprisingly, the general beak of the order can contain cycles - for example, dove A pecks dove B, which pecks dove C, which pecks dove A.

Prove that any finite set of pigeons can be arranged in a row from left to right so that each pigeon pecks a pigeon right from the left.

Since this is a question of graph theory, the first things that came to my mind were simply asking for the topological type of relationship graphs (relationships are the hierarchy order). What made it a little more complicated is that there can be a cyclic relationship between pigeons. If we have a cyclic dependence as follows:

A-> B-> C-> A

where A pecks on B, B pecks on C and C returns and clings to A

If we present it in accordance with the proposed problem, we have the following: CBA

But the above row ordering does not affect the hierarchy between C and A.

I had a different idea of ​​solving it using mathematical induction, where the base case for two pigeons arranged according to their hierarchy order, assuming that the order of the beak order is valid for n pigeons, and then proves that this is true for n + 1 pigeons.

I'm not sure I'm wrong here. Some information on how I should analyze this problem would be helpful.

thanks

Answer 1

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

• for k = 2, it obviously holds
• let k = n always require order, we prove that it exists for n + 1. Choose and order any n pigeons (A1> A2 ...> An) from the given n + 1. And let C be (n + 1) pigeon.
  If C pecks A1, then it can be added to the beginning of the line and the statement is proved. If A1 inserts C, then it compares C with A2 - if C pecks A2, then it can be inserted between A1 and A2 and the statement is satisfied. If not, repeat that the comparison process to the last pair is A (n-1) and An, as the 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, you can insert it at the end of the "line".

QED

PS Note that "switching cycles" do not necessarily exist - if we assign the number of pigeons from 1 to n and assume that the pigeon pecks another, if its number is greater, then we can obviously arrange them in a row but not in a circle, so that every dove pecks its left neighbor.

PPS This proof also provides an algorithm for constructing the required order.

Answer 2

Have you considered building a directed graph and then looking for the Hamiltonian path that visits each point (pigeon) once? The Hamiltonian path should show consistency - this is not proof. Just a solution.