165年前的任务困扰着数学家

1850年，牧师托马斯·柯克曼，英国数学家和兰开夏郡教区的神父，配制在娱乐杂志上的无辜的前瞻性益智数学爱好者“笔记本电脑的女士们，先生们”：

“十五的年轻女学生外出散步七天三行：你需要每天安排“这样一来，同一对女学生就不会在同一行见过两次面。”

该任务看起来很简单，但是如果您尝试解决它，您会立即意识到事实并非如此。您可以尝试用铅笔和纸解决此问题，或尝试使用HTML版本。

由于其错误的简单性，该任务很快成名。爱好数学的人发表了他们的决定，科学家发表了科学文章，试图制定出解决该问题的一般方法。

结果，这个难题帮助塑造了数学的新领域：组合方案，现在专门针对这本厚厚的教科书。。最初是将人们分成小组（或最终被称为方案）的简单任务，如今已成为一种方法，用于实验设计，计算机科学，密码学，农业，体育，甚至赌博欺诈中的纠错码（有一个故事，一个犯罪集团在七年内通过购买彩票的可能组合，在46个彩票中有6个彩票中有6个彩票中有6个彩票中的5个赚了七百万美元，如果彩票的成本低于在46个彩票中赢得5个奖金的额外奖金加上赢得大奖的可能性）。

例如，用于解决错误的经典汉明代码使用关于女学生的问题的解决方案（创建三名女学生的小组，其中不重复任何一对），但仅适用于七个女学生（位）的方案。


（7、3、2）的法诺飞机

最令人惊讶的是，在165年中，数学家一直无法以一般的方式解决问题。他们仍然无法给出答案，在初始条件下该谜题的解决方案是什么：有n个女学生，您需要创建大小为k的组，这样，每组t个女孩在同一组中从未相遇两次。这样的表述称为方案（n，k，t）。

例如，对于一个由19个女孩组成的小组，可能有超过110亿个三胞胎，其中每对仅相遇一次。这个数字就是答案。但是随着女生数量的增加，选择的数量呈指数增长。

显然，该问题在某些条件下已解决，而在其他一些条件下未解决。例如，如果所有可能对的三胞胎由六名女学生组成，则该问题显然无法解决（与女学生安雅有五对可能，同时，每个三胞胎与安雅有两对，其中五对没有分成两对）。也就是说，根据可除性原理，许多选项（n，k，t）立即被消除。

同时，存在（n，k，t）完全符合可除性原理，但仍无解：例如（47，3，2）。

在过去的几年中，该解决方案因许多组合（n，k，t）而闻名通过代数或在计算机上蛮力检查的文件。但是，如何以一般方式解决此问题，该如何处理（47，3，2）之类的异常呢？如何理解问题是否有解决方案？耶路撒冷希伯来大学的数学家吉尔·凯莱（Gil Kalai）在接受Wired采访时说

，长期以来，这项任务一直被认为是组合学中最著名的问题之一。他回想起一年半前与同事争论的情况，他们得出的结论是“我们永远不会知道答案，因为任务显然太复杂了。” 然而，仅仅两周后，来自牛津大学的年轻数学教授彼得·基瓦什（Peter Keevash）证明了Kalai是错的。在科学文章中

从2014年1月开始，他认为，如果满足除数条件，几乎总是存在解决问题的方法。在2015年4月发表的一篇新论文中，他展示了如何计算给定参数的近似解数。

没有人期望将概率论应用于该问题的解决，但是这种方法效果很好。

回到彩票，骗子意识到可以通过购买46个中的5个的所有组合（当表示46个中的6个时）来减少所购买彩票的数量，然后他们将获得绝对所有的额外奖品，并且还可能获得大奖。尽管还没有计算出方案（46、6、5），但仍有一些方案对于实际应用而言足够接近。其中之一可能是由犯罪集团使用的。

新计算电路的数量不断增长。他们中的许多发现实际应用中，像（15，3，2）从经典的问题，和（46，6,5） 。带有图表的1000页指南出炉了。但是，数学家对于如何确定针对特定给定条件的解决方案仍然不知所措。多亏了Kivash，我们才知道这样做的可能性很高。因此，至少现在清楚的是，对于所有未知数，寻找解决方案总比放弃它更好。此外，还有用于生成任何参数的采样电路的工具。

但是由于Kivash的工作，希望可以开发出一种方法来创建准确的任何参数的方案。如果发生这种情况，那将是数学上的非凡突破。

但是，Kivash的工作纯粹是理论上的。专家说，根据他的方法创建实用的算法将需要几代数学家的辛勤工作。

Source: https://habr.com/ru/post/zh-CN380785/