Pigeonhole原理（離散數學）

Question

我不理解這個問題，我的意思是我想知道這個問題的樣本輸入輸出，問題是：「鴿子的原理規定，如果一個函數f有n個不同的輸入但小於n個不同的輸出，則存在兩個輸入a和b，使得a = b和f（a）= f（b）。給出一個算法來找到a和b，使得f（a）= f（b）該函數輸入是1,2，......，和n？

我無法解決，因爲我不認清這個問題這個問題。 尋求你的幫助。

Answer 1

繼續什麼https://stackoverflow.com/a/42254627/7256243說。 可以說y將長度爲N的數組A映射到長度爲N-1的數組B. 比結果可能是一個數組B;爲1索引你會有2個元素。

A = {1,2,3,4,5,6} 
map A -> B 

可能的解決方案可能是。

B= {1,2,{3,4},5,6} 

A - >的映射可以通過多種方式完成。 這裏在這個例子中，數組A中的3和4的輸入索引在數組B中具有相同的索引。

我希望這個有用。

Answer 2

那我們一步一步來吧。

我有2個盒子。我的父親給了我3塊巧克力....

我想把這些巧克力放在2盒。爲了我們的利益，我們來命名巧克力a,b,c。

那麼我們可以將它們放入多少種方式？

[ab][c] 
[abc][] 
[a][bc] 

你看到一些奇怪的東西？至少有一個盒子含有1個以上的巧克力。

那麼你怎麼看？

你可以嘗試任何數量的盒子和巧克力（超過盒子數量），試試這個。你會看到它是正確的。

好吧，讓我們更容易：

我有5個朋友3個房間。我們正在舉辦派對。現在讓我們看看會發生什麼。 （我所有的朋友都會坐在房間裏的任何一個）

我聲稱至少有一個房間會有超過1個朋友。

我的朋友們相當混亂，知道他們試圖證明我錯了。

• 朋友-1選擇房間1。
• 朋友2認爲爲什麼房間1？然後，我會是正確的，所以他選擇房間2
• 朋友3也認爲相同...他避開1和2房間，並進入房間3
• 朋友4現在來了，他明白，沒有其他空房間，所以他不得不進入一些房間。因此我變得正確。

那麼你瞭解情況？

有n個朋友（功能），但不幸或（幸運的是）他們的房間（輸出值）小於n。所以ofcourse的一個存在2朋友礦井a和b誰共享同一個房間。（同值f(a)=f(b)）

Answer 3

鴿巢原理說，如果你有超過箱子更多的項目，盒子中的至少一個必須有其中有多個項目。

如果您想要查找！= b具有屬性f（a）== f（b）的項目，直接的方法是使用散列映射數據結構。使用函數值f（x）作爲鍵來存儲項目值x。迭代項目，x = 1，...，n。如果在f（x）處沒有條目，則存儲x。如果存在，則x的當前值和f（x）中存儲的值是您正在尋找的一對類型。

僞代碼：

h = {} # initialize an empty hashmap 
for x in 1,...,n 
    if h[f(x)] is empty 
     h[f(x)] <- x # store x in the hashmap indexed by f(x) 
    else 
     (x, h[f(x)]) qualify as a match # do what you want with them 

如果你想找出所有鴿子誰擁有室友，初始化與空套HashMap中。然後遍歷這些值並將當前值x附加到由f（x）索引的集合中。最後，遍歷hashmap並挑選出所有具有多個元素的集合。

---

既然你沒有指定一個語言，它的樂趣，我決定在Ruby中實現後者的算法：

N = 10 # number of pigeons 

# Create an array of value/function pairs. 
# Using N-1 for range of rand guarantees at least one duplicate random 
# number, and with the nature of randomness, quite likely more. 
value_and_f = Array.new(N) { |index| [index, rand(N-1)]} 

h = {} # new hash 

puts "Value/function pairs..." 
p value_and_f # print the value/function pairs 

value_and_f.each do |x, key| 
    h[key] = [] unless h[key] # create an array if none exists for this key 
    h[key] << x    # append the x to the array associated with this key 
end 

puts "\nConfirm which values share function mapping" 
h.keys.each { |key| p h[key] if h[key].length > 1 } 

將會產生以下的輸出，例如：

Value/function pairs... 
[[0, 0], [1, 3], [2, 1], [3, 6], [4, 7], [5, 4], [6, 0], [7, 1], [8, 0], [9, 3]] 

Confirm which values share function mapping 
[0, 6, 8] 
[1, 9] 
[2, 7] 

由於此實現使用隨機性，因此每次運行它時都會產生不同的結果。