Geek asks and answers

The algorithm for finding ten integers> 0, which are summed up to 2011, but their sum of inverse sums is 1

find ten integers> 0 that add up to 2011, but their total hits are 1

eg.

x1 + x2 + .. + x10 = 2011

1 / x1 + 1 / x2 + .. + 1 / x10 = 1

I found this problem here http://blog.computationalcomplexity.org/2011/12/is-this-problem-too-hard-for-hs-math.html

I was wondering what computational complexity is and what types of algorithms can solve this problem.

EDIT2: I wrote the following brute force code, which is fast enough. I did not find any solutions, although I need to tweak my assumptions a bit. Now I'm sure I will find a solution.

 from fractions import Fraction

pairs = [(i,j) for i in range(2,30) for j in range(2,30)]

x1x2 = set((i+j, Fraction(1,i)+Fraction(1,j)) for i,j in pairs)

print('x1x2',len(x1x2))

x1x2x3x4 = set((s1+s2,f1+f2) for s1,f1 in x1x2 for s2,f2 in x1x2 if f1+f2<1)

print('x1x2x3x4',len(x1x2x3x4))

count = 0
for s,f in x1x2x3x4:
    count+=1
    if count%1000==0:
        print('count',count)
    s2 = 2011 - s
    f2 = 1 - f
    for s3,f3 in x1x2:
        s4 = s2-s3
        if s4>0:
            f4 = f2-f3
            if f4>0:
                if (s4,f4) in x1x2x3x4:
                    print('s3f3',s3,f3)
                    print('sf',s,f)
+3
source share
5

, , , O (1), . .

. 10- , .

  • x 1, x 2,..., x 10
  • x 1 <= x 2 < =... <= x 10
  • , , xi
    • S = x 1 +... + x i
    • R = 1/x 1 +... + 1/x i
    • , S <= 2011 - (10 - i) * x i
    • , R <= 1 - (1/[(2011 - S)/(10 - i)])
    • , , . , , , x i <= x + 1

. , , , x 1,..., x 10 , 960. x i, 960, x i, . , , 1/x 1 +... 1, , 960/x 1 +... 960. , , . , , , .

+2

(#), , - . ( ) . , , N. , , "" (10, 2011).

2011 :

  • 10 : 2, 4, 5, 80, 80, 80, 160, 320, 640, 640
  • 11 : 3, 6, 4, 12, 12, 24, 30, 480, 480, 480, 480
  • 13 : 2, 4, 5, 200, 200, 200, 200, 200, 200, 200, 200, 200, 200
  • 15 : 3, 6, 6, 12, 16, 16, 32, 32, 32, 64, 256, 256, 256, 512, 512

- , ?

using System;
using System.Collections.Generic;

namespace Recip
{
    class Program
    {
        static void Main(string[] args)
        {
            int year = 2011;
            int numbers = 20;

            int[,,] c = new int[year+1, numbers+1, numbers];

            List<int> queue = new List<int>();

            // need some initial guesses to expand on - use squares because 1/y * y = 1
            int num = 1;
            do
            {
                for (int i = 0; i < num; i++)
                    c[num * num, num, i] = num;
                queue.Add(num * num);
                num++;
            } while (num <= numbers && num * num <= year);

            // expand
            while (queue.Count > 0)
            {
                int x0 = queue[0];
                queue.RemoveAt(0);
                for (int i = 0; i <= numbers; i++)
                {
                    if (c[x0, i, 0] > 0)
                    {
                        int[] coefs ={ 20, 4, 2, 2, 3, 3};
                        int[] cons = { 11, 6, 8, 9, 6, 8};
                        int[] cool = {  3, 2, 2, 2, 2, 2};
                        int[] k1   = {  2, 2, 4, 3, 3, 2};
                        int[] k2 =   {  4, 4, 4, 6, 3, 6};
                        int[] k3 =   {  5, 0, 0, 0, 0, 0};
                        int[] mul =  { 20, 4, 2, 2, 3, 3};

                        for (int k = 0; k < 6; k++)
                        {
                            int x1 = x0 * coefs[k] + cons[k];
                            int c1 = i + cool[k];
                            if (x1 <= year && c1 <= numbers && c[x1, c1, 0] == 0)
                            {
                                queue.Add(x1);
                                c[x1, c1, 0] = k1[k];
                                c[x1, c1, 1] = k2[k];
                                int index = 2;
                                if (k == 0)
                                {
                                    c[x1, c1, index] = k3[k];
                                    index++;
                                }
                                int diff = index;
                                while (c[x0, i, index - diff] > 0)
                                {
                                    c[x1, c1, index] = c[x0, i, index - diff] * mul[k];
                                    index++;
                                }
                            }
                        }
                    }
                }
            }

            for (int n = 1; n < numbers; n++)
            {
                if (c[year, n, 0] == 0) continue;
                int ind = 0;
                while (ind < n && c[year, n, ind] > 0)
                {
                    Console.Write(c[year, n, ind] + ", ");
                    ind++;
                }
                Console.WriteLine();
            }
            Console.ReadLine();
        }
    }
}
+1

Choose(2011,10) 10^26 10 , 2011 . , , , .

, .

. 10^7.

-, , . , , . , , .

, , :

  • , , , . , .

  • , . 1, 1.

xi.

-, , 1.

, #:

static int[] x = new int[10];
static void Search(int depth, int xi, int sum, double rsum) {
    if (depth == 9) {
        // We know exactly what the last number should be
        // to make the sum 2011:
        xi = 2011 - sum;
        // Now check if the sum of reciprocals adds up as well
        if (Math.Abs(rsum + 1.0 / xi - 1.0) < 1e-12) {
            // We have a winner!
            x[depth] = xi;
            var s = string.Join(" ", Array.ConvertAll(x, n => n.ToString()));
            Console.WriteLine(s);
        }
    } else {
        int lastxi = xi;
        // There are 2 ways xi can be too large:
        xi = Math.Min(
            // 1. If adding it (10 - depth) times to the sum
            // is greater than our total:
            (2011 - sum) / (10 - depth),
            // 2. If adding (10 - depth) times its reciprocal
            // is less than 1.
            (int)((10 - depth) * remainder));
        // We iterate towards smaller xi so we can stop 
        // when the reciprocal sum is too large:
        while (xi >= lastxi) {
            double newRSum = rsum + 1.0 / xi;
            if (newRSum >= 1.0)
                break;
            x[depth] = xi;
            Search(depth + 1, xi, sum + xi, newRSum);
            xi--;
        }
    }
}
Search(0, 1, 0, 0)
+1

If you used brute force algorithm to repeat all combinations, you will get answers. But I don’t think it’s quite as big as 10 * 2011 * 2011. Since you can easily arbitrarily postulate that x1

I think the brute force approach will get an answer easily. However, I would suggest that the instructor is looking for a mathematical approach. I think that “1” should have some meaning with respect to how to manipulate the equations for the answer. "2011" seems arbitrary.

0
source

More articles:


All Articles