IBM Ponder This史上最难谜题:给出谜底猜谜面

    2009年2月份IBM Ponder This的谜题可能是从98年谜题月赛开办以来最难的谜题。谜题发布一个月之后仍然没有任何人答对,主办人不得不宣布延迟一个月,并再三增加提示。最终,答对此题的仍然只有7个人。很久没有看到如此精彩的谜题了,有兴趣的网友不妨试一试。
    题目非常有趣。传统的谜题是给出谜面求解谜底,但这个谜题则恰恰相反:下面这一串数字是某个问题的答案,你能猜出这个问题是什么吗?这串数字里有一个错误在哪里?

900F 80F0 8F00 80CA BE12 AA90 9400 0048 3E5B 8AC0
3400 00CB BC81 8A08 3C00 0050 BE43 00C0 3E00 A019
8059 BE13 2000 0092 BE9B 2A0B 2A00 8052 8841 04C0
3E00 840B 084B 0098 E000 8819 845A 8012 0300 0050
826F 0500 0600 846E 8264 0900 0A00 8065 0C00 0072
A054 8368 8569 4800 4400 8573 4200 4100 8349 8542
2800 2400 854D 2200 2100 9F00 E000 8888 8444 8000
0030 0DED 8222 0050 0060 8444 8222 0090 00A0 8000
00C0 0DED A000 8333 8555 4080 4040 8555 4020 4010
8333 8555 2080 2040 8555 2020 2010 8300 8500 8030
8050 0880 0840 8050 0820 0810 8030 8050 0480 0440
8050 0420 0410 8500 8030 8050 0280 0240 8050 0220
0210 8030 8050 0180 0140 8050 0120 0110 90F0 9F00
E000 8888 8444 8000 0003 0DED 8222 0005 0006 8444
8222 0009 000A 8000 000C 0DED A000 8333 8555 4008
4004 8555 4002 4001 8333 8555 2008 2004 8555 2002
2001 8300 8500 8003 8005 0808 0804 8005 0802 0801
8003 8005 0408 0404 8005 0402 0401 8500 8003 8005
0208 0204 8005 0202 0201 8003 8005 0108 0104 8005
0102 0101 9F00 8030 8050 8003 8005 0088 0084 8005
0082 0081 8003 8005 0048 0044 8005 0042 0041 8050
8003 8005 0028 0024 8005 0022 0021 8003 8005 0018
0014 8005 0012 0011 80FF 8F0F A333 8000 5000 0DED
8000 3000 0DED A333 C555 1800 1400 C555 1200 1100
8F0F A333 A555 1080 1040 A555 1020 1010 A333 A555
1008 1004 A555 1002 1001

Read more…

Harvard-MIT Mathematics Tournament 2009: Guts Round

摘录几道题目。

计算1·2^2 + 2·3^2 + 3·4^2 + … + 19·20^2
原式 = (1^3 + 2^3 + … + 20^3) – (1^2 + 2^2 + … + 20^2) = 44100 – 2870 = 41230

求2^x = 3^y – 1的所有正整数解
x=1时(1,1)是一个解;当x>1时,方程模4后左边永远等于0,右边则是(-1)^y – 1,可知y为偶数。令y=2z,那么有2^x = (3^z – 1)(3^z + 1),这就要求3^z-1和3^z+1都是2的幂;但它们只相差2,因此它们只有可能是2和4,于是z=1,即原方程的另一个解为(3,2)。

圆周上有2008个点。选择两个点连成一条线,再选另外两点连一条线,这两条线段相交的概率为多少?
给定四个点,在三种连接方案中恰有一种会发生相交。取遍所有C(2008,4)种组合,相交的总情况数总是占了1/3,因此所求的概率就是1/3。

Read more…

这些序列都是自相似序列……

    如果说数学家是魔术师的话,无穷就是一根最强大的魔杖。在Manfred Schröder的一篇题为Fractals in Music的论文里,作者提到,把每个正整数对应的二进制数中“1”的个数依次写下来,得到的数列有一个很神奇的性质:划掉所有的奇数项,得到的序列仍然是整个序列本身。

十进制数  1   2   3    4    5    6    7     8     9    10    11    12    13    14
二进制数  1  10  11   100  101  110  111  1000  1001  1010  1011  1100  1101  1110
1的个数   1   1   2    1    2    2    3     1     2     2     3     2     3     3
取偶数项      1        1         2          1           2           2           3

    最初我是在《算法艺术与信息学竞赛》里见到这个东西的,当时硬是被震撼住了。这样的序列叫做“自相似序列”,意思是说自己的一部分等于本身。注意到,这个“自相似”可以无限制地进行下去。再次取出所得的序列中的偶数项,结果还是与最初的序列一样;再这样做下去做无数次,每一次的结果都会与原始序列相同。也就是说,无穷里面包含了无穷多个规模不同的无穷,并且所有这些无穷都和原来完全相同。不过呢,仔细一想你会发现这个一点也不奇怪,奥妙就在于,n和2n的二进制表达中唯一的差别就是末尾的那个“0”。

Read more…