Harvard-MIT 竞赛题

Osullivan

1计算1·2^2 + 2·3^2 + 3·4^2 + ... + 19·20^2

2求2^x = 3^y - 1的所有正整数解

3圆周上有2008个点。选择两个点连成一条线，再选另外两点连一条线，这两条线段相交的概率为多少？



4我们称一个正整数为“吉祥数”，如果它的二进制表达中有偶数个“1”。第2009个吉祥数是多少？

5在3*3*...*3的n维立方体棋盘中，选取三个排成一条线的小立方体有多少种可能？

答案晚上给出哦~~~~~~
先做做看~~~~~~~~

zhy3729

哇！！  看来高中水平是解决不了了

Osullivan

原帖由 zhy3729 于 2009-6-9 18:18 发表
哇！！  看来高中水平是解决不了了

基本上高中都可以解决吧

Osullivan

计算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

aben306

这个没看懂哦....顶一下吧.回头再细看.

123wyx

题目不错，活而不难。
第二题x=1,y=1或x=3,y=2,没有其他正整数解

咖啡味的茶

1、某人已给出方法。2、x=1,y=1或x=3,y=2。3、跟据题意，四点位置都互异，不管四点怎么取，线连接方式有三种，相交只有一种，所以概率是1/3。4、没懂意思，麻烦楼主讲清楚。5、可以把每个立方体理解为n维坐标系的格点。那么取三个格点成为直线的概率是：由于两点确定一条直线，所以任取两点第三点就确定了，取法是3^n*(3^n-1)/6，所有三点取法是3^n*(3^n-1)*(3^n-2)/6，相除得1/(3^n-2)。

superacid

第二题给一个想法：
3^y-2^x=1
首先，(1,1),(3,2)是解，如果有其他解，必然x>3,y>2
两边mod4得y是偶数，进而可以推出x是奇数。
y=2t, x=2s+1
3^(2t)-1=2^(2s+1)
(3^t-1)(3^t+1)=2^(2s+1)
所以3^t-1,3^t+1都是2的幂
t只能等于0,1，矛盾。
所以解只有(1,1),(3,2)

conwood

概率学的不好，不做了。

2求2^x = 3^y - 1的所有正整数解
正整数解只有两组，如6楼所言。
至于为什么
首先，如果y是偶数，比如y=2z，那么3^y-1=(3^z+1)(3^z-1)=2^x
要想让3^y-1是2的幂，必须(3^z+1)和(3^z-1)都是，而(3^z+1)=2+(3^z-1)，显然，z足够大时，这是不成立的。
如果y是足够大的奇数，可以证明3^y-1除以4的余数是2，因此也不能是2的幂


4我们称一个正整数为“吉祥数”，如果它的二进制表达中有偶数个“1”。第2009个吉祥数是多少？
可证明，2^n内有2^(n-1)-1个吉祥数，因此可以知道从1到4096里有2047个吉祥数，往前数一下，数到2009个就行了。

superacid

第4题对任意n，
2n和2n+1中有且只有一个吉祥数，
所以第2009个吉祥数是2*2009或2*2009+1，
而2009写为二进制是11111011001，是吉祥数。
所以第2009个吉祥数是5018