MathematiKa’11第6名!

MathematiKa是印度IIIT每年一度举办的数学/计算机竞赛。你只要准备一张纸一支笔一个人脑(你自己的)还有一台图灵机即可。算上今年它已经举办了4届了,而我们Kleber队从一开始就一直在参加。我,啊C,余超,去年和今年还加了小林。

今年的成绩是历届之中最好的一次,是第6名。7题只有1题没有做出来,而且我们强烈怀疑那题有问题(……)。

简单说一下题目。

第一题是解密码,这是余超的专长。简单来说就是有封加了密的电子邮件,全部都是0和1,里边有答案,要你把答案求出来。因为有给人名,所以余超一开始就用固定格式猜出来了这个是变长编码。然后一般来说这种变长编码都是前缀码,实验表明应该是按照频度的一个Huffman编码。然后余超用“余超的方法”(这是个专有名词!),把信件除了答案的大部分都弄出来了。答案的两个单词首字母是ra***** n*****,然后余超就上课去了……接下来我猜n应该是number(余超也是这样想的),然后ra******应该是一个人名。联想到出题的是印度人,果断我就google了一下Ramanujan number,输进去,果断对了。

以下是密文:

1101001010100010 0011101001111101001010100010
11000001010 1010011100111011110100010 11001001 1100000101100011 10111010010000101000111100011010010111 01100011 001010101101111010011100001101110101010100111 0111000011101111000000100010
001001010001110100010110100011 01110110110001100111

第二题是3SAT,是经典的3SAT的代数化方法,不过要反过来,从多项式化成3SAT。一般的情况是困难的,但是这里题目比较好人,很容易就把正确的求出来了。题目用了一个很大的平方项来控制每个变量都是0或者1,只要把这个搞懂,之后就很容易了。

第三题是变态题。简单来说的话是一个rewrite system,有十几条规则,都是说如果有某几个素因子的话就将这几个素因子换成另外几个这样的规则,然后从2开始,每次选择最前面的一条规则执行,规则如下:

7*13 -> 17
5*17 -> 2*3*13
3*17 -> 19
2*19 -> 23
3*11 -> 29
29   -> 7*11
23   -> 5*19
19   -> 7*11
17   -> 1
13   -> 11
11   -> 13
2*7  -> 3*5
2    -> 3*5
1    -> 5*11

题目给出了一堆数,问这些数会不会出现。

其实如果将素因子的重数看成counter的话,不难发现这就是一个counter machine,是图灵等价的,所以简单的找规律是不行的。但是又一次题目很好人,给的数里边很多2的次方,这令人不禁怀疑2的次方有什么特殊之处。将这些次方输出之后,会发现这个counter machine只会经过2的质数次方。稍加分析就将所有可能的数推出来了。

第四题数学题,不难,啊C瞬间做出来了。

第五题求所有\mu(n)=-1(默比乌斯函数)的n的四次方倒数和,精确到10位小数。一开始我以为很难,要弄Zeta函数之类的东西,后来发现不用,数据规模小,直接暴力即可……SB了大概半个小时……

第六题明显佩尔方程,我们很多人都做出来同一个答案,但是系统说答案错……几个相邻的解也试了,没有一个行的……这也就是我们没做出来的题……非常怨念……

第七题啊C做的,貌似就是菲波那契数有关的某求和,据啊C说一开始他试的答案被系统拒绝了,但是后来有人做出来之后他再试一次就对了……这个果断是那边的人在乌龙……而且貌似Global Test的时候也出过这题,数据不同,但是没有人做出来……

当然这里题目简介的话,我做的题目明显写得更详细,不过不代表别的题目容易……像第七题,光是看我就看了好久都不明白……

怎么说,现在题目越来越有趣了,比当年多样化多了,竟然还有了密码题……不过Gordian Knot上也见过所以不算太吃惊~~~

总的来说这次还是挺有趣的~~~

EDIT: 证实了第六题果然有问题……怨念啊……

Advertisements

One thought on “MathematiKa’11第6名!

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s