一道IMO题目

wayne

计算一万组,我花了10个小时,https://nestwhile.com/res/OEIS/A386855.txt
给定y. $a^2+b^2=(1+ab)y$都是genus=0的曲线,只要找到曲线上的一个有理点,就能得到参数解.Maple有个parametrization命令.

maple的在线帮助: https://www.maplesoft.com/suppor ... s%2Fparametrization
算法原理是 For a description of the method used see M. van Hoeij, "Rational Parametrizations of Algebraic Curves using a Canonical Divisor", 23, p. 209-227, JSC 1997.
我下载下来了,放在了:https://nestwhile.com/res/ebook/ ... %28Z-Library%29.pdf

wayne

以$y=241$为例: 可以转化成 $(2 a-b y)^2-(y^2-4) b^2-4 y=0$ ,也就是$X^2-58077 Y^2-964Z^2=0$
使用eclib的solve_legendre工具:

1. zuse@konrazes-iMac Downloads % solve_legendre
   
2. Solving ax^2 + by^2 + cz^2 = 0
   
3. Using method 4
   
4. 
   
5. Enter coefficients a b c: 1 -58077  -964
   
6. 1 -58077 -964
   
7. Solution: (x:y:z) = (369:1:9) --OK
   
8. x = [369,-360,151812] * [u^2,uv,v^2]
   
9. y = [-1,48,388] * [u^2,uv,v^2]
   
10. z = [9,306,-3852] * [u^2,uv,v^2]
    
11. Disc(qx) = -223944912
    
12. Disc(qy) = 3856
    
13. Disc(qz) = 232308
    
14. Parametric solution is OK
    
15. Enter coefficients a b c:

复制代码

得到$[2 a - 241 b,b]=[\frac{369 u^2-360 u v+151812 v^2}{9 u^2+306 u v-3852 v^2},\frac{-u^2+48 u v+388 v^2}{9 u^2+306 u v-3852 v^2}]$ , 也就是$[a,b]=[\frac{4 \left(16 u^2+1401 u v+30665 v^2\right)}{9 \left(u^2+34 u v-428 v^2\right)},\frac{-u^2+48 u v+388 v^2}{9 \left(u^2+34 u v-428 v^2\right)}]$
如果设$U=\frac{2 (167 v-17 u)}{7 u+314 v}$,就能得到$[a,b]=[\frac{U^2-610 U+73504}{9 \left(U^2-241 U+1\right)},-\frac{64 U^2+2 U-305}{9 \left(U^2-241 U+1\right)}]$ ,跟maple的计算完全一致

mathe

里面legendre theorem很不错，也就是我们不需要求出参数解，只需要判断一些二次剩余是否等于1即可，这个效率远远高于求解

wayne

不过legendre theorem 实现起来也不麻烦, 我还是试了下. 结果一致.不到10分钟就跑完了10000组.

1. idx=0;pool=Association[];
   
2. Block[{bc,y},Monitor[Do[bc=Table[Times@@(Select[FactorInteger[d],Mod[#[[2]],2]==1&][[All,1]]),{d,{y^2-4,y}}];If[AllTrue[bc,#>1&],
   
3. If[AllTrue[{Length@Solve[x^2==bc[[1]],x,Modulus->bc[[2]]],Length@Solve[x^2==bc[[2]],x,Modulus->bc[[1]]]},#>0&],pool[++idx]=y];If[Length[pool]==100,Break[]]],{y,1,10^6}],{idx,y}]];pool

复制代码

wayne

此题背景介绍:

1988年在澳大利亚堪培拉举办的 IMO 上的第 6 题，颇有些传奇色彩，出题者是联邦德国（West Germany）的 Stephan Beck。著名的数学教育家 Arthur Engel 在他的著作《Problem-Solving Strategies》描述了这道题到底有多难：澳大利亚的试题委员会收到试题后，没有一人能够限时解出，其中包括有名的 Georges Szekeres 和他的妻子，两个人都是解题高手。于是主委会把这道题提交给澳大利亚的四位数论专家，同样均无法在6个小时内做出，这道题也被标记上“极难”。但是主委会经过很久的讨论之后，仍然把这道题放在了当年的最后一题，也许是他们相信“江山代有人才出”吧。

最后的结果就是造就了当时IMO有史以来最难的题目（直到后来被2017年第3题“隐形的兔子”超越），总共 268 名参赛选手，居然有 189 名选手 0 分，6 分的题目平均分仅为 0.634。甚至从小被称为数学小天才的“陶哲轩”在这道题上也仅拿到 1 分（虽然他还是以 34 分的总分拿到了金牌），不过要知道这一年陶哲轩才刚刚 13 岁，而且已经是参加过两届 IMO 的元老级选手（分别拿到铜牌和银牌，银牌那届也很有意思，后面我们会讲到）。之后陶哲轩前往美国求学，21 岁获得博士学位，24 岁成 UCLA 终身教授，31 岁获菲尔兹奖，陶哲轩的名气也让人们回忆起这道题目时津津乐道。

不过幸运的是，“长江后浪推前浪”确实出现了，在这些选手中，真的有 11 名选手满分做出了这道题！其中就包括两名中国选手：四川彭县中学的何宏宇（满分金牌），和上海复旦大学附中的陈晞。当中还包括后来同样获得菲尔兹奖的越南选手吴宝珠（也是满分金牌）。不过不论是陶哲轩，还是其它满分选手，在这届比赛上的光芒都被一位来自保加利亚的选手 Emanouil Atanassov 所盖过，因为他不仅满分做出了这道题，还因为解法特别简洁美妙，获得了当年的特别奖（Special prize）。