啄食鸽子的顺序？

Question

我正在探讨Ericksson教授从我的母校发布的关于图论的问题,并且遇到了这个相当独特的问题,关于鸽子及其形成啄食命令的先天倾向.问题如下:

每当一群鸽子聚集在一起时,他们本能地建立一个啄食顺序.对于任何一羽鸽子,一只鸽子总是啄另一只鸽子,使它远离食物或潜在的配偶.无论其他鸽子在哪里,即使经过多年的分离,同一对鸽子也会选择相同的啄食顺序.令人惊讶的是,整体啄食顺序可能包含周期 - 例如,鸽子A啄B鸽,啄鸟鸽C,啄鸟鸽A.

证明任何有限的鸽子都可以从左到右排成一排,以便每只鸽子立即将鸽子啄到左侧.

由于这是关于图论的一个问题,我想到的第一件事就是要求拓扑关系的图形(关系是啄食顺序).让这更复杂的原因是鸽子之间可能存在循环关系.如果我们有一个循环依赖如下:

A-> B-> C->甲

其中A啄B,B啄C和C后退并啄A

如果我们以问题建议的方式表示它,我们有如下内容:CBA

但上面给出的行排序并不考虑C和A之间的啄食顺序.

我有另一个想法是通过数学归纳解决它,其中基本情况是根据它们的啄食顺序排列的两只鸽子,假设啄食顺序排列对n只鸽子有效,然后证明它对于n + 1只鸽子是真的.

我不确定我是否会走错路.关于如何分析这个问题的一些见解将会有所帮助.

谢谢

Answer 1

我会证明确实使用感应(a> b表示peacks b):

1. 对于k = 2,它显然是成立的
2. 让k = n总是需要顺序,让我们证明它存在于n + 1.从给定的n + 1中选择并订购任何n只鸽子(A1> A2 ...> An).让C成为第(n + 1)羽.
   如果C啄A1,那么它可以被添加到"线"的开头并证明了陈述.如果A1啄C然后让C与A2比较 - 如果C啄A2,那么它可以插入A1和A2之间并且语句成立.如果不是 - 重复比较过程直到最后一对 - A(n-1)和An,随着过程进行,我们假设A(n-1)> C.如果C> An,则可以在A(n-1)之间插入C )和An,如果不是 - 它可以插入"行"的末尾.

QED

PS请注意,"啄食周期"并不一定存在 - 如果我们将鸽子数量从1分配给n并假设鸽子啄食另一个如果他的数量更大那么我们显然可以在线排序而不是在圈子中排序以便每只鸽子啄他的离开了邻居.

PPS该证明还给出了构造所需顺序的算法.