关于鸽子洞原理(离散数学)这道题怎么解决？

Question

我不明白下面这道题的意思。我的意思是我想知道这道题的样本输入输出。"鸽子洞原理指出如果一个函数f有n个不同的输入但少于n个不同的输出,那么存在两个输入a和b,使得a!=b和f(a)=f(b). 提出一种算法来寻找a和b，使f(a)=f(b)。假设函数输入为1,2,......,n。"?

我无法解决这个问题，因为我没有理解清楚这个问题.寻求您的帮助。

Answer 1

好吧，我们一步一步来。

我有2个盒子。我爸爸给了我3块巧克力......。

我想把这些巧克力放在两个盒子里。为了我们的利益，让我们把巧克力命名为 a,b,c.

所以我们可以用多少种方式把它们放进去？

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

你看到一些奇怪的东西了吗？至少有一个盒子里有不止一块巧克力.

所以，你觉得呢？

你可以尝试用任何数量的盒子和巧克力（多于盒子数量）并尝试这个。你会发现这是正确的。

好吧，让我们把它变得更容易。

我有5个朋友，3个房间。我们正在举行一个聚会。现在让我们看看会发生什么。(我所有的朋友将坐在任何一个房间)

我声称至少有一个房间会有一个以上的朋友。

我的朋友们很调皮，他们知道这一点，他们试图证明我错了。

• 朋友1选择了1号房。
• 朋友-2认为为什么选择1号房？那我就对了，所以他选择了2号房。
• 朋友3也是这样想的......他避开1号和2号房，进入3号房。
• 朋友-4现在来了，他明白没有其他的空房间，所以他必须进入某个房间。这样我就变得正确了。

所以你明白这种情况吗？

有n个朋友（功能），但不幸或幸运的是，他们的房间（输出值）小于n。a 和 b 同房者。f(a)=f(b))

Answer 2

鸽子洞原理说，如果你的物品比盒子多，那么至少有一个盒子里一定有多个物品。

如果你想找到哪些项a !=b具有f(a) == f(b)的属性，一个直接的方法是使用hashmap数据结构。 使用函数值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

如果你想识别 都 有室友的鸽子，用空集初始化哈希图。 然后迭代值，并将当前值x追加到由f(x)索引的集合中。 最后，遍历哈希图，挑出所有有一个以上元素的集合。

---

由于你没有指定语言，为了好玩，我决定用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]

因为这个实现使用了随机性，所以每次运行它都会产生不同的结果。

Answer 3

继续 https:/stackoverflow.coma422546277256243。 说。假设你将一个长度为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 ->的映射可以通过任何方式完成.在这个例子中，Array A中的输入索引3和4在Array B中都有相同的索引。

我希望这有用。