趣题:选出最多的大小为奇数的子集,使得两两的交集大小都是偶数

    在集合 {1, 2, …, n} 中选出尽可能多的子集,使得每个子集所含的元素个数都是奇数,但是任意两个子集的交集都含有偶数个元素。那么,我们最多能够选出多少个这样的子集来?

    容易看出,我们至少可以选出 n 个子集。例如,当 n = 4 时, {1} 、 {2} 、 {3} 、 {4} 就满足要求。我们还能选出更多的子集来吗?简单地尝试后,你会觉得似乎不行。不过,这却并不是显然的,因为存在一些不那么平凡的方案,也能让子集的数量达到 n ,例如 {1, 2, 3} 、 {1, 2, 4} 、 {1, 3, 4} 、 {2, 3, 4} 这 4 个子集也是满足要求的。看来,证明最多只能选出 n 个子集,好像并不那么容易。

Read more…

趣题:所有人手上的糖数最终会变得一样多

    n 个小朋友在圆桌上坐成一圈。初始时,每个小朋友都拥有一定数量的糖。接下来,反复进行下面两个操作:

      1. 如果有人手里的糖数是奇数,就向老师再要一颗糖,把手里的糖数补成偶数;
      2. 每个人都把自己手中一半的糖传给他右边的人(同时接到从左边传过来的糖)。

    证明:总有一个时刻,所有小朋友手中都会拥有相同数量的糖。
    附加题:这是一个非常经典的问题。猜猜看我最早在什么地方看到的这个问题?

Read more…

经典证明:能否在平面上写下不可数个不相交的Y?

    这篇文章收录了 Which Way Did the Bicycle Go 趣题集中一个非常有趣的问题:是否有可能在平面上画不可数个不相交的 8 ?答案是否定的。证明方法非常简单。对于任意一个 8 字形,在两个洞里各取一个有理点 P 、 Q (由于平面上的有理点是稠密的,这是总能办到的),则称这个 8 字形圈住了有理点对 (P, Q) 。注意到由于 8 字形不能相交,因此两个 8 字形不可能圈住同一对有理点。由于平面上的有理点对是可数的,因此 8 字形的数量也是可数的。

      

    注意到,平面上显然能够容下不可数个不相交的直线段,也显然能够容下不可数个不相交的圆(比方说一系列同心圆)。在 Mathematical Puzzles 一书里, Peter Winkler 提出了这样一个问题:我们能在平面上写下不可数个不相交的字母 Y 吗?

      

Read more…

趣题:只用一把带有两条平行边的直尺作图

    在下面的问题中,你不能使用圆规,只能使用直尺作图。不过,你的直尺拥有两条平行边,你可以在作图时同时使用它们。你需要充分利用直尺的这个特点,完成下面几个作图任务。

      1. 作出已知角的角平分线;
      2. 作出已知线段的中点;
      3. 作出已知圆的圆心;
      4. 过已知点作已知直线的平行线。

    假设你的直尺是无限长的。直尺的宽度是固定不变的。直尺不能用来度量长度。

Read more…