x1,x2,…,xn 之和为 pq，可分为和相等的 p 组，又可分为和相等的 q 组，求 n 的最小值

abc666zs

一道预赛压轴题，如图

cgl_74

这两天分析，没有完全解决此问题，但是有了一定进展，并有下一步的思路：
我没有研究过图论，所以此题我就按照通常思路，从最基本的理论开始分析。可能有一些繁琐。
一、已经证明，对于任意给定的p, q, 满足q > p且 (p , q) =1；那么必定存在p+q-1个自然数，满足分组A：q个p；以及满足分组B：p个q。这个通过辗转相除法，以及构造归纳证明得出结论。

二、但是p+q-1是否是最少的数？这个我还在确定一些细节。现在的思路如下：
        1、对于任意一个分组A（q个p）和分组B（p个q），总可以通过逐步调整方法，保持总的数字的数目不增加，保持q个p和p个q的要求，并且B分组中p行数据中，每一行都至少有一个数字p。那么我可以通过迭代和数学归纳法证明，p+q-1就是最少的数目。
        2、现在正在确定1部分的一些细节。

三、对于p, q的一些特殊形式，比如q = p*k + 1或q = p*k - 1时，结论成立。这个相对好证明。

abc666zs

恳求老师们的答复

abc666zs

恳求老师们的答复

cgl_74

我这2天看看，周末给你一个答复。
其它大侠有时间也可看看。

abc666zs

cgl_74 发表于 2024-5-15 19:06
我这2天看看，周末给你一个答复。
其它大侠有时间也可看看。

感激不尽！

wilsony

这是数论竞赛题？

abc666zs

wilsony 发表于 2024-5-17 12:22
这是数论竞赛题？

他标答给的是图论解法，但是我很好奇他是否有代数解法

王守恩

abc666zs 发表于 2024-5-17 18:07
他标答给的是图论解法，但是我很好奇他是否有代数解法

能把标答给的图论解法,   拿出来大家分享分享？  谢谢！

abc666zs

王守恩 发表于 2024-5-17 18:39
能把标答给的图论解法,   拿出来大家分享分享？  谢谢！

记分成的组数为u1，u2……u41。v1，v2……v49，若存在xk同时属于ui，vj，便在ui，vj间连一条线，得简单图G，对于G的最大连通分支G’，设G’中含有a个顶点ui，b个顶点vj，则所有出现在ui中的项必同时出现在vj（否则G’非最大连通分支），有49a＝41b，所以a+b≥90，n≥89。当x1＝……＝x41＝41，x42＝……x81＝8，x82＝……＝x89＝1时取等

abc666zs

王守恩 发表于 2024-5-17 18:39
能把标答给的图论解法,   拿出来大家分享分享？  谢谢！

老师，因为我暂时还没有深度的学习图论，所以里面的一些专业术语我不是很懂，原理也并非很明确，可能存在笔误，请多多包涵