离散数学趣味题目

1、加泰罗尼亚语号码

吃完饭，姐姐洗碗，姐姐把姐姐洗好的碗一个个放进柜子里。成对有n个不同的碗，洗之前叠一叠。可能是因为姐姐贪玩，碗没有及时带进柜子，姐姐把洗好的碗堆在一边:

-
——
——————
———

(1)待洗(2)待堆放(3)堆放

关于小姐姐最后堆出来的碗堆，我有多少种方法可以问？

本主题的解决方案与此相同:

一队不同的汽车在街上行驶。他们随时可以拐进死胡同加油，然后出来加入队伍。当你最终离开城镇时，有多少种可能的汽车排队形式？

呵呵，想想，挺有意思的！

[简要分析]

这是一个有趣的组合问题。组合数学是离散数学的一部分，研究组合计数。图论本来是组合数学的一部分，后来才分离出来:)。组合的一个指导技巧是，如果一个过程的计数没有研究好，可以找一个与之一一对应的过程，这个过程研究的相对比较好。那不是很美吗？

你看，如果有n个碗，我姐每边放一个，画一个“(”；如果姐姐叠一个，画一个“)”；如果姐姐不贪玩，一放下就可以收起来，字符串是“()()()……()”，对吧？现在你想想，下次我来说答案:)。
车队也是如此。汽车进胡同就画“()”，出来就画“()”，但不进胡同的就画“()”。呵呵，所以给出了同样的解决方案。

离散的问题很有技巧。问题的解决方案一看就是不规则的，好像是量身定做的，但是也有指导思想吧？

2.拉姆齐问题

用简单的方式描述:

r(p，Q)是任意给定人群中必须有P人认识或者Q人不认识的最小人数。比如r (3，3) = 6，也就是说任意数量的人，至少6个人，当然可以满足3个人认识或者3个人不认识。R(p，q)称为拉姆齐数。

图论的描述:

用红色和蓝色边给一个完整的图G着色，每条边一种颜色。因此，要么是所有对角线都是红色的红色P形，要么是所有对角线都是蓝色的蓝色Q形。能保证上述结果的G的最小顶点数，就是Ramsay数r(p，q)。

经过几代人的努力，在计算机的帮助下，人类现在正在寻找的九个非凡的拉姆齐数是:

r(3，3)=6，r(3，4)=9，r(3，5)=14
r(3，6)=18，r(3，7)=23，r(3，8)=28
r(3，9)=36，r(4，4)=18，r(4，5)=25

呵呵，试试吧。你能给出什么拉姆齐数的推理过程？

[背景趣闻]

关于寻找拉姆齐数的难度，匈牙利数学家鄂尔多斯用了如下类比:
某年某月某日，一群外星土匪入侵地球，扬言如果一年内找不到R (5，5)就灭绝人类！面对决一死战，人类应该集合全世界所有的数学家和计算机专家，不分昼夜地计算R (5，5)，以拯救人类免于灭绝。如果外星人想让我们得到R (6，6)，我们别无选择，只能开战，试一试:)。

3.梦中情人

约翰的梦中情人有金色的头发，蓝色的眼睛，苗条的身材和高大的身材。他认识阿黛尔、贝蒂、卡罗尔和多丽丝，其中一个是约翰的梦中情人。(1)只有三位女士眼睛是蓝色的，身材很瘦。(2)只有两个是黄头发，个子高；(3)只有两个又瘦又高。(4)只有一个是蓝眼睛黄头发。(5)阿黛尔和贝蒂的眼睛颜色一样。(6)贝蒂和卡罗尔的发色相同(7)卡罗尔和多丽丝的身材不同(8)多丽丝和阿黛尔的身高相同。这四个人中谁是约翰的梦中情人？

【简单分析】

呵呵，显然这是一个数理逻辑问题。我们可以建立一个形式化的模型来分析它，也可以用一个简单的推理过程来做。很有意思，这就是离散数学的魅力！