我如何解决有关鸽子原理（离散数学）的问题？

Question

我不明白下面的问题。我的意思是我想知道这个问题的示例输入输出："The pigeonhole principle states that if a function f has n distinct inputs but less than n distinct outputs,then there exist two inputs a and b such that a!=b and f(a)=f(b). Present an algorithm to find a and b such that f(a)=f(b). Assume that the function inputs are 1,2,......,and n.?"

由于我没有清楚地理解问题，因此无法解决此问题。寻求您的帮助。

Answer 1

继续所说的内容。假设您将长度为 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 个朋友。

我的朋友们都很恶作剧，他们知道这一点后试图证明我是错的。

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

所以你了解情况了吗？

有n个朋友（functions）但不幸或（幸运）他们的房间（输出值）小于n。所以当然有我的 2 个朋友 a 和 b 共享同一个房间。（相同的值 f(a)=f(b)）

Answer 3

鸽巢原则说，如果你的物品多于箱子，那么至少有一个箱子必须有多个物品。

如果要查找哪些项 a != 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]

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

我如何解决有关鸽子原理（离散数学）的问题？

How do I solve this question about Pigeonhole Principle (Discrete Mathematics)?

algorithm

discrete-mathematics

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

好吧，让我们让它变得更简单：