一个基督教文科大学,EST。1846

神秘圣诞老人问题仍然存在

  • 项目类型: 导演
  • 针对项目贡献者: 项目贡献者:丹尼尔起重机,皮匠染料

目的/抽象

我们探讨了秘密圣诞老人的礼物交换的问题。一组n人随机抽取的名字,给人一种礼物画的人。首先,我们考察了在各种情况下的礼物交换的可能性时,大家一下子吸引名称。那么我们考虑某些礼物交换的可能性,当人们轮流绘图名称和制定战略,最大限度地从最慷慨的参与者接收礼物的可能性。

引入/背景

秘密圣诞老人的礼物交换是一种流行的圣诞传统。在一个秘密圣诞老人的礼物交换,一组n人随机抽取的名字,与一个人不能得出他或她自己的要求。然后每个人给的礼物,画的人。

有几种方法来设计一个秘密圣诞老人的礼物交换。这些礼物交换完成之前的工作[2,5,6,9,10]通常假定每个人都是同样可能给的礼物给任何其他人的礼物交换,这是真实的,当每个人都在画一个名字下运行一旦。第2节中,我们总结了一些这些结果,并也适用于其他情况下,以神秘的圣诞老人证明的结果。我们认为,每个人都为单一的情况下,如果所有参与者都在大小为k的家庭,并在参与者可在不同尺寸的家庭。需要重绘名的概率取决于家庭规模的时候,我们不允许家人送礼物给对方。车多项式允许这种概率的计算。其他技术,如容斥原理和范围上矩阵的永久可用于研究他限制这些概率的行为时,参与者在礼物交换的数量增加。

接下来,在第3节,我们考察允许礼物交换的可能性时,在名称,而不是一下子在第2节时绘制一个,然后我们确定哪些交流是比他人更容易。具体而言,我们表明,绘制名称的顺序会影响到谁每个参与者最有可能给的礼物。在这个typeof运算礼物交换,任何一个紊乱的概率可以写成涉及指示器功能方面的产品,这使我们能够概率比较两个不同的送礼者 - 受体对。我们发现,每个人是最有可能给直接在他面前画的人,第一人画是最有可能得到的礼物的最后一个人画画。此外,我们发现,过去的人画更可能给礼物第二到最后一个人比任何其他送礼的收件人对。

方法

资源/链接

[1]巴顿,D.E.,\匹配分布:泊松限制性形式和近似的衍生方法”。 皇家统计学会会刊。 B系列,20(1):73-92,1958。

[2]博伊德,A.V.,和J.N.里德利,\秘密圣诞老人的回报。” 数学公报,85(503):307-311,2001。

[3]格里马尔迪,拉尔夫页。 离散和组合数学。第4版。波士顿:艾迪生韦斯利朗文,1998年。

[4] margolius,巴巴拉小时。 “吃饭,吃饭的客人匹配问题”。 数学杂志,76(2):107-118,2003。

[5]麦奎尔,凯利米。,乔治mackiw,和Christopher小时。莫雷尔。 “神秘圣诞老人问题”。 数学公报,83(498):467-472,1999。

[6] penrice,斯蒂芬克,\紊乱,永久物,和圣诞礼物”。 在美国数学月刊,98(7):617-620,1991。

[7]斯赫雷弗,一个。 “MINC猜想的简短证明。”组合理论系列杂志,25(1978)80-83。

[8]面包车皮棉,J.H。 “票据上的范德瓦尔登猜想egoritchev的证明。”线性代数及其应用,39(1981)1-8。

[9]病房,托尼\ dierence方程,决定因素和秘密圣诞老人问题”的数学公报,89(514):2-6,2005年。

[10]白色,马修J.,\神秘圣诞老人问题。”玫瑰技术豪曼本科数学学报,7(1)(纸5),2006年的研究所。