数学家和物理学家的巴黎

24

任务

1. 让每个男生与不少于$m$个女生交友，每个女生与不超过$m$个男生交友（$m$为任意自然数）。证明在这种情况下满足匹配定理的条件。

2. 小学生围成一圈解决问题。结果，每个人解决了 4 个问题，每个问题由 4 个小学生解决。证明可以组织问题的分析，使每个学生只解决一个问题，并且分析所有问题（一次）。

3. 给出了传输网络。包含输出但不包含输入的顶点集称为网络切割。切割$B$的能力是数量$c(B)$，等于$B$中包含的打击数​​量。如果 $\phi$ 表示流量，则 $|\phi|$ 将表示流量的大小。证明对于任意流 $\phi$ 和任意割 $B$，以下变换成立：$|\phi| \leq c(B)$。

4. 切 $B$ 调用最小值，如果其容量 $c(B)$ - 所有切割的吞吐量中最小的。使用Ford-Falkerson算法，推导出最小割的吞吐量等于最大流的值 - max $|\phi| = \min c(B)$ （福特-福克森定理）。

5. 检查如果$\phi$是最大流，则统一所有未标记顶点（使用Ford-Falkerson方法基于流$\phi$制作标签）获得的割是最小的。

6. 证明任意两个最小割的并集和交集也是最小割。

7. 证明未标记顶点的割（对于最大流）是所有最小割的并集。由此推断，该切割不依赖于用于产生流的最大切割。

文学

1. A. Kofman、R. Faure，威尔从事运筹学，《世界》，1966 年。
2. K. Berge，图论及其应用，伊利诺伊州，1962 年。
3. L. Ford、D. Folkerson，网络流动，世界，1966 年。
4. O. Ore，图论，Hayka，1968。
5. D. Gale，线性经济模型理论，伊利诺伊州，1963 年。

数学和物理学家巴黎

在巴黎，许多建筑都与过去几个世纪杰出科学家的记忆有关。此外，卢浮宫曾经是国王的据点，在 1789 年革命之前成为学者们的聚会场所。尽管后来在拿破仑一世的统治下，卢浮宫成为了一座博物馆，但即便如此，一些科学家仍驻扎在那里。勒让德的一封信被保存下来，在信中这位数学家请求住在宫殿的旧部分。

巴黎有一些街道以数学家、物理学家和天文学家的名字命名，但这些科学家并不都是法国人。这些名字是：勒让德、罗莫尔、帕斯卡、皮埃尔·居里、玛丽·居里、兰伯特、布丰、富兰克林、卡诺、阿拉戈、笛卡尔、莱布尼茨……

短语“数字$z$是两个数字$x$和$y$中较大的一个”可以使用以下公式编写：

$$z = \frac{1}{2} (|x - y| + x + y).$$

“数字$u$是三个数字$x, y$和$z$中最大的”这句话怎么写？

证明单词 ABABAB 可以被 7 整除（A 和 B 是任意数字）。

足球问题

如您所知，足球杯比赛是按照所谓的奥林匹克制度进行的：负者被淘汰，如果负者则进行重赛。

那一年没有重赛，有75支球队参加了比赛。

进行了多少场杯赛？