父亲，两个儿子，999幅画

本文关键字：两个 儿子 999幅画 父亲 | 更新日期: 2023-09-27 18:25:13

这是一个针对作业申请的问题："一个父亲有两个儿子和999幅画。每幅画都有不同的价值：第一幅画值1，第二幅画值2，以此类推，直到最后一幅画值999。他想把所有的画分给他的两个儿子，这样每个儿子都能得到同等的价值。999幅画有多少种方法可以做到这一点？例如：如果父亲有7幅画，他可以通过给长子画1、6和7来公平地分配。次子得2、3、4和5。两者的总和值相等，14。如果有7幅画，父亲可以公平地将它们分为4种方式（此处未列出其他3种），因此解决方案为4。提示：这个数字可能很大，所以请将最后10位数字和您的解决方案草图发送给我们。"

我所做的是尝试使用暴力方法，通过编写一个c#程序来添加所有可能的组合，该程序编写自己的c#程序，并在循环中循环，如下所示：

StringBuilder sb = new StringBuilder();
for (short i = 2; i <= 999; i++) //starts from 2 because 1 is always added to the total for one side
{
    sb.AppendLine("for (byte i" + i.ToString() + " = 0; i" + i.ToString() + " < 2; i" + i.ToString() + "++)");
    sb.AppendLine("{");
}
for (int i = 2; i <= 999; i++)
{
    sb.Append("if (i" + i.ToString() + " == 1) { total += " + i.ToString() + "; }'n");
}
for (short i = 2; i <= 999; i++)
{
    sb.AppendLine("}");
}

然后将其添加到结果中的if块之后：

if (total == 249750)
{
    count++; //count is a BigInteger
}
total = 1;

从技术上讲，这种方法应该有效（在少量画作上进行了测试），但问题是，这是一个巨大的数字，用这种方式在我的电脑上计算结果大约需要一百万年。。。有没有一些数学技巧可以在合理的时间内做到这一点？

父亲，两个儿子，999幅画

更容易解决更一般的问题，即确定第一个儿子可以通过多少种方式获得值k，其中k是一个参数。找出恰当的概括是一门艺术；它是在名为动态编程的算法课程中教授的。

设x为变量。需要的数学见解是，对于n绘画，多项式乘积中的x^k系数

x (1 + x^2) (1 + x^3) ... (1 + x^n)

in x是长子可以获得值CCD_ 7的方式的数目（包括值1的绘画）。这是因为该产品分发给

(sum for i_2 = 0 to 1) (sum for i_3 = 0 to 1) ... (sum for i_n = 0 to 1)
    x^(1 + 2 i_2 + 3 i_3 + ... + n i_n),

这就是您的暴力解决方案评估该产品的有效方式。这里的动态程序相当于一个接一个地分配因子，而不是一次分配所有因子，例如

x (1 + x^2) = x + x^3
x (1 + x^2) (1 + x^3) = (x + x^3) (1 + x^3)
                      = x + x^3 + x^4 + x^6.
x (1 + x^2) (1 + x^3) (1 + x^4) = (x + x^3 + x^4 + x^6) (1 + x^3)
                                = x + x^3 + x^4 + x^6 + x^4 + x^6 + x^7 + x^9
                                = x + x^3 + 2 x^4 + 2 x^6 + x^7 + x^9.

节省的时间来自于重复的条款。我们现在只有六个任期，而不是八个任期（二次方三次方）。

只保留最后十位意味着我们可以在取10^10为模的整数环中计算这个乘积。因此，我们可以将中间系数减少到该数字的模，以避免使用bignums。这一技巧在竞争编程界是众所周知的，在抽象代数或数论课程中也有正式的介绍。

在Mathematica:

In[1]:= Coefficient[x Product[1+x^i,{i,2,7}],x^(Sum[i,{i,1,7}]/2)]
Out[1]= 4
In[2]:= Coefficient[x Product[1+x^i,{i,2,8}],x^(Sum[i,{i,1,8}]/2)]
Out[2]= 7

在Java中：

public class PartitionPaintings {
    public static void main(String[] args) {
        long[] p = new long[] {0, 1};
        for (int i = 2; i <= Integer.parseInt(args[0]); i++) {
            long[] q = new long[p.length + i];
            for (int k = 0; k <= p.length - 1; k++) {
                for (int j = 0; j <= 1; j++) {
                    q[k + i * j] = (q[k + i * j] + p[k]) % 10000000000L;
                }
            }
            p = q;
        }
        System.out.println(p[(p.length - 1) / 2]);
    }
}

这是一项数学工作。

你基本上是在寻找一个数字分区，一个有不同部分的分区。

所有画作的总价值是整数1…999的总和。根据高斯的(n * (n+1)) / 2，我们得到：(999 * 1000) / 2 = 499500。因此，每个儿子都应该得到总价值249750的画作。

现在，我们只需要找到具有不超过999的不同部分的该值的分区数。我们将找到的每个分区分配为一个儿子的一组绘画，第二个儿子将获得剩余的绘画（总价值相同）。

因此，唯一棘手的部分是计算不同和有界部分的配分函数。但我想你也可以通过编程来实现这一点。

德黑兰谢里夫理工大学的Mohammadreza Bidar实际上写了一篇论文，标题很有希望"将整数划分为不同的有界部分、恒等式和有界"。你可以在INTEGERS第12卷中阅读（这是那里的第8篇文章）。

相关文章：