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] 

由于此实现使用随机性，因此每次运行它时都会产生不同的结果。