某个导师要和 A 、 B 两名学生玩一个游戏。导师会把 A 、 B 两名学生分别放进两间小黑屋里，每间屋子里都有一台电脑，这两台电脑之间只有一条通信线路。然后，导师会想一个正整数 n （可能会非常非常大），把它的值告诉这两名学生；再构造出集合 {1, 2, …, n} 的两个子集，分别交给这两名学生。于是，每个人都知道了 n 的值和 {1, 2, …, n} 的一个子集。两人需要合作确定出，他们手中的集合是否包含公共的元素。他们之间交流信息的唯一途径就是那条通信线路，但他们能够使用的流量是有限的。具体能够使用多少 bit 的流量，这可以由他们自己决定，但必须在游戏开始之前（也就是 n 的值确定之前）就定好并告诉导师。 和其他类似的问题一样，在游戏开始之前，两人可以商量一个对策。不过，这一回，两人商量了很久，始终无法找到一个必胜的对策。就在两人快放弃的时候，他们突然发现，两人的通信线路上存在一个“漏洞”：两人都可以不计流量地访问一台特殊的第三方机器，我们不妨把它叫做机器 O 。不过，机器 O 只能做一件事情：从 A 那儿读取一个 1 到 n 的排列，从 B 那儿读取一个 1 到 n 的排列，然后计算出这两个排列复合之后是否恰好含有一个循环，并将计算结果分别告知 A 和 B 。然后，机器 O 就会自动关机，再也不能访问了。也就是说，A 和 B 只能使用机器 O 一次。注意， […]

    下面是 IBM Ponder This 2013 年 5 月的谜题：写一个程序来计算 f(x) = 1 + x + x2 + x4 (mod 2233393) 。你的程序只能使用以下三种语句，其中等号表示赋值，变量 2 和变量 3 的位置都可以用常量来代替： (1) 变量 1 = 变量 2 + 变量 3 (2) 变量 1 = 变量 2 * 变量 3 (3) 变量 1 = 变量 2 mod 变量 3     很容易想到，一种最基本的解法如下： a = x […]

    这是一个非常有趣的问题，它出自 UyHiP May 2013 的谜题。     假设你有 n 枚外观完全相同的硬币，它们的重量分别为 1g, 2g, 3g, …, ng 。有意思的是，这一次，你已经知道了各枚硬币的重量，而且你也已经把重量值标在了这些硬币上。但是，由于我不知道各枚硬币的重量，因此我希望你能向我证明，你所标的重量值是正确的（我知道这些硬币的重量是从 1 克到 n 克，我只是不知道哪个硬币对应哪个重量）。     你唯一能用的工具就是一架天平。每一次，你可以任意选择一枚或多枚硬币，放在天平的左侧，再从剩下的硬币中任意选择一枚或多枚硬币，放在天平的右侧（注意，你只能在天平上放硬币，不能放别的东西）。一个有意思的问题是，为了向我证明你所标的重量值都是对的，你最少需要使用多少次天平？     显然，为了证明 n 枚硬币的重量标签的正确性，我们最多需要称 n – 1 次。先把硬币 1 放在左边，把硬币 2 放在右边，让对方看到硬币 1 确实比硬币 2 要轻。接下来，向对方验证硬币 2 确实比硬币 3 更轻，硬币 3 确实比硬币 4 更轻，等等。称完 n – 1 次后，我们就相当于给出了 n 枚硬币的轻重顺序，因而它们只有可能分别是 1 克 、 2 克 、 3 […]

从同事那里借来了一本单墫教授主编的《初等数论》奥数书，看到很多精彩的问题，在这里做个笔记，与大家一同分享。不少问题和答案都有过重新叙述，个别问题有所改动。   问题：找出所有使得 2n – 1 能被 7 整除的正整数 n 。 答案：由于 2n 的二进制表达为 1000…00 （n 个 0），因此 2n – 1 的二进制表达为 111…11 （n 个 1）。而 7 的二进制表达是 111 ，要想让它整除 n 个 1 ，显然 n 必须是也只能是 3 的倍数。

    Using your Head is Permitted 数学谜题站的主持人 Michael Brand 某日收到了来自 R. Nandakumar 的一个谜题：是否有可能把一个矩形剖分成若干个小矩形，使得每个小矩形的形状互不相同，但它们的面积都一样？没有想到，从这个问题出发，加上一些非常机智巧妙的分析与构造，我们能得到越来越多有意思的东西。于是，它就变成了 Using your Head is Permitted 今年 3 月的谜题。看了谜题的答案后，我也被彻底折服，决定把这一系列的思考重述在此，和大家一同分享。为了简便起见，下面的“矩形剖分方案”一律指的是把一个大矩形分割成若干个小矩形的方案。