啄食鴿子的順序？

我打算通過problems從圖表理論Prof. Ericksson從我的alma-mater張貼，並遇到這個相當獨特的問題，關於鴿子和他們天生的傾向，形成啄食訂單。現在的問題去如下：啄食鴿子的順序？

每當鴿子的羣體聚集，他們本能地建立啄食順序。對於任何一羽鴿子來說，一羽鴿子總是啄食另一隻鴿子，使其遠離食物或潛在的配偶。同一對鴿子總是選擇相同的啄食順序，即使是經過多年的分離，無論其他鴿子在哪裏，都會選擇。出人意料的是，整體啄食訂單可以包含循環 - 例如，鴿甲啄鴿子B，其啄鴿子C，其啄鴿子A.

證明任何有限集合鴿子可以佈置在一個從左邊排到右側，這樣每個鴿子立即向左側啄鴿子。

由於這是一個關於圖論的問題，我想到的第一件事就是要求拓撲排序的關係圖（關係是啄食順序）。是什麼讓這個更復雜一點是鴿子之間可能存在循環關係。如果我們有一個循環依賴如下：

A-> B-> C->一個

其中上B A啄，B啄上的C和C返回並啄上的一個

如果我們代表它由提出問題的方式，我們有話如下： CBA

但上面給出的行排序並在C和A

之間啄食順序不是因素我有另一個想法通過數學歸納解決它基本情況是兩隻鴿子根據其啄食順序排列，假設啄食順序安排對n只鴿子有效，然後證明它對於n + 1只鴿子是正確的。

我不知道我是否在這裏走錯了路。我應該如何分析這個問題的一些見解將會有所幫助。

由於

來源

2010-06-16 sc_ray

不是我的專業領域，從我簡單化的邏輯來說，如果它是循環的或循環的，那麼顯然它們不能在一條直線上從左到右排列。相互關聯的圈子，可能與奧運標誌類似，但不是直排。 – MJB 2010-06-16 14:47:07

如果你有4羽鴿子，那麼有6羽鴿子。線性形式將涉及其中三個對。所以你將不得不忽略一些配對。按照我的理解，這個任務表明你總是可以選擇配對來產生線性順序，而不是表示所有配對的線性順序。 – 2010-06-16 14:47:56

3羽鴿子的週期性案件也讓我感到疑惑，但後來我再次檢查了這個問題的措辭： >每隻鴿子都立即向左邊啄鴿子。這似乎並不是要求C左側有任何東西，只要你可以把鴿子排成一排*，這樣鴿子左邊就會有另一隻鴿子啄它。所以'C B A'將會是有效的，就像'B A C'一樣，就像'A C B'一樣。同樣，如果你有'A-> B'，'A-> C'和'B-> C'，將鴿子排成一排不能傳達'A-> B'和'A-> C '。但是'C B A'是這種情況下的唯一答案。有趣的問題！ – shambulator 2010-06-16 14:50:46

我將證明，使用感應確實（A> B指peacks B）：

對於k = 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，則C可以插入到A（n-1 ）和An，如果不是的話 - 它可以插入到「行」的末尾。

QED

附：請注意，「啄食週期」並不一定存在 - 如果我們將鴿子數量從1到n分配，並且假定如果鴿子的數量多於其他鴿子，那麼我們顯然可以按順序排列它們，但不能將它們排成一行，這樣每個鴿子就會啄他左鄰居。

P.P.S.該證明也給出了構建所需順序的算法。

來源

2010-06-16 14:51:27 Vladimir

很棒的回答。我在想同樣的觀點。該問題詢問是否可以安排有限集合，而證明確實如此。謝謝！ – 2010-06-16 16:40:34

你有沒有考慮構建一個有向圖，然後尋找哈密爾頓路徑，每次訪問每個點（鴿子）？哈密爾頓路徑應該揭示序列 - 但這不是一個證明。只是一個解決方案

來源

2010-06-16 14:54:40 Grembo

啄食鴿子的順序？

回答

相關問題