Problem of paired sums from two sets of numbers

[ramsey2879]

Let A(n) = {1,2,3,4, … 8} and B(n) = {1,2,3,4, …. 16} be two sets of consecutive integers with no repetition.

Divide the set of elements B(n) into two subsets C(n) and D(n) each comprising 8 different integers and such that every element of B(n) is used with the condition that 8 equations of the form A(i) + C(i) = D(i) can be simultaneously formed without using any element of A(n), C(n) and D(n) more than once.

There are 48 unique solutions each involving the additional limitation that the numbers 1 and 2 from B(n) are associated with the number 1 from A(n) to form the equation 1+1=2 as one of the 8 forms A(i) + B(i) = C(i). I haven’t counted the total number of possible solutions without this added limitation.

For added complexity, there is a number B(k) in B which can be put into D(n) as above. Then the following sets can be created A`(n) = A(n) + 9; C`(n) = C(n) + B(k); and D`(n) = D(n) less B(k) + 17 and 18, such that there are nine elements in each set and 9 simultaneous equations of the form A`(i) + C`(i) = D`(i) can be formed without repeating an element of A`, C` or D`. Determine what the value of B(k) must be and give a solution for a set of 9 simultaneous solutions (there is only one solution for B(k) ). To illustrate this problem, the set A(n) could have been the set {1,2,3,4} and B(n) could have been {1,2,3,..8} since the problem works with any multiple of 4 for A(n), e.g
1+1 = 2
2+4 = 6
3+5 = 8
4+3 = 7

Here the number 5 can be added to A(n) and 9,10 added to B(n). In this case the number
B(k) = 7 and the new sets are.

1+1 = 2
2+4 = 6
5+3 = 8
4+5 = 9
3+7 = 10

 

[ramsey2879]

Patterns to solve the problem

Let A(n) = {1,2,3,4, … 8} and B(n) = {1,2,3,4, …. 16} be two sets of consecutive integers with no repetition.

No one tried my problem, but I think it is interesting because using patterns just involving the odd numbers for C(n) see below you have 3/4 ths of the prpblem solved. Does anyone see a pattern involving the even numbers?

results:

8 1 4 5 3
10 1 4 7 5 3
16 1 10 3 4 11 9 7 5
18 1 10 3 4 13 11 9 7 5
24 1 14 3 4 5 12 17 15 13 11 9 7
26 1 14 3 4 5 12 19 17 15 13 11 9 7
32 1 20 3 4 5 12 7 16 23 21 19 17 15 13 11 9
34 1 20 3 4 5 12 7 16 25 23 21 19 17 15 13 11 9
40 1 28 3 4 5 20 7 16 9 12 29 27 25 23 21 19 17 15 13 11
42 1 28 3 4 5 20 7 16 9 12 31 29 27 25 23 21 19 17 15 13 11
48 1 30 3 4 5 28 7 12 9 16 11 24 35 33 31 29 27 25 23 21 19 17 15 13
50 1 30 3 4 5 28 7 12 9 16 11 24 37 35 33 31 29 27 25 23 21 19 17 15 13

 

[Playdo]

Can you generalize your problem to sets of natural numbers in general? I think if you use arrays to sort of visualize the additive table you will see that you can write a general summation formula. It is an interesting combinatorics problem.

 

[ramsey2879]

Can you generalize your problem to sets of natural numbers in general? I think if you use arrays to sort of visualize the additive table you will see that you can write a general summation formula. It is an interesting combinatorics problem.

Glad you asked. I don't have enough of a math background to write a general formula; perhaps it can be done using a matrix computation for the lower values. I don't think there is a general formula since there are at least seven different solutions for each m > 5.

I did see a pattern as per my last post and wrote an Excel basic program that solves the problem by trying the lowest possible choices sequentially for the remaining m values of C(2), C(4), C(6), C(8) ... up to C(2m). If there is no fit for say C(2j) given all the prior choices the program substitutes the next higher choice for C(2j-2). This is a self teaching program. Once one solution for a given m is found, the next solution, if there is one; is found by deleting the choice for C(2m) and forcing a higher value for the next prior choice, i.e., C(2m-2). If there is no immediate solution, the self teaching program begins backtracking further until it can go on to find the next solution or until the value of C(2) becomes so high that no higher value is possible. Using this program I found that the number of solutions for m = 1 to 14 is respectively 1,1,1,1,1,7,9,53,89,425,1005,7189, 17745 and 173104. Since there are more than one solution for m > 5, I doubt that there is a general solution formula. For m > 8, there is at least one solution for C(2) having any value selected from 4m to 6m -2. The sum of the m intergers of each solution set C(m) is always (3m^2 + 7m + 4) so this is a partitioning problem in part as well as a combinatorics problem. But there is a catch, the m integers in the partition set must be different from each other and be selected from the set consisting of (i) all multiples of 4 from 4 to 4m and (j) all multiples of 2 from 4m + 2 to 6m-2. The value of B(2m), i.e., 6m, is too high because no number can be added to it to obtain another B(i). There are thus a total of 2m-1 integers in the selection set for the partitioning problem. There are (2m-1, choose m) possible sets out of these numbers and there are m! permutations of each possible partition set. Thus I find it remarkable that there is only one solution each for m = 1 up to 5.

As you can see, I reduced the problem as originally posted (where there are 8m numbers from 1 to 8m in set B(m)) to one where there are 2m numbers in the set B(m), but they are no longer consecutive.

 

[Playdo]

Glad you asked. I don't have enough of a math background to write a general formula; perhaps it can be done using a matrix computation for the lower values. I don't think there is a general formula since there are at least seven different solutions for each m > 5.

I did see a pattern as per my last post and wrote an Excel basic program that solves the problem by trying the lowest possible choices sequentially for the remaining m values of C(2), C(4), C(6), C(8) ... up to C(2m). If there is no fit for say C(2j) given all the prior choices the program substitutes the next higher choice for C(2j-2). This is a self teaching program. Once one solution for a given m is found, the next solution, if there is one; is found by deleting the choice for C(2m) and forcing a higher value for the next prior choice, i.e., C(2m-2). If there is no immediate solution, the self teaching program begins backtracking further until it can go on to find the next solution or until the value of C(2) becomes so high that no higher value is possible. Using this program I found that the number of solutions for m = 1 to 14 is respectively 1,1,1,1,1,7,9,53,89,425,1005,7189, 17745 and 173104. Since there are more than one solution for m > 5, I doubt that there is a general solution formula. For m > 8, there is at least one solution for C(2) having any value selected from 4m to 6m -2. The sum of the m intergers of each solution set C(m) is always (3m^2 + 7m + 4) so this is a partitioning problem in part as well as a combinatorics problem. But there is a catch, the m integers in the partition set must be different from each other and be selected from the set consisting of (i) all multiples of 4 from 4 to 4m and (j) all multiples of 2 from 4m + 2 to 6m-2. The value of B(2m), i.e., 6m, is too high because no number can be added to it to obtain another B(i). There are thus a total of 2m-1 integers in the selection set for the partitioning problem. There are (2m-1, choose m) possible sets out of these numbers and there are m! permutations of each possible partition set. Thus I find it remarkable that there is only one solution each for m = 1 up to 5.

As you can see, I reduced the problem as originally posted (where there are 8m numbers from 1 to 8m in set B(m)) to one where there are 2m numbers in the set B(m), but they are no longer consecutive.

Yeah it looks like you are playing around with a problem related to the subset-sum problem from computability theory.

Given a set of natural numbers S and a target natural number n, determine if any subset of S of size m adds to the target n.

Example

{1,4,4,6,7} target equals 9

m=1 ><
m=2 ><
m=3 1+4+4
m=4 ><
M=5 ><

Generalizing that you might start simply with a general set S of size k and then yes. I believe there is a formula, the comp sci guys have been working on things like that for 30 years. It might be under the general heading of the N=NP problem related to time complexity of algorithms. With some things there will be formula for special cases, but then not in the general case.

Well for instance factor N when N = 2*x^2, well clearly it's 2,x,x. But factor N in general, ... nobody knows how to do that.

 

[ramsey2879]

Yeah it looks like you are playing around with a problem related to the subset-sum problem from computability theory.

Playing around sounds trite but it is fun and relaxing, and there just might yet be some further insight into numbers yet to be gained.
Define the master group M(n) to comprise the following 2n members: all multiples of 2 from 2 to 2n and all integers from 2n+1 to 3n.
I find that for every integer n, there is an ordered subgroup {a(i)} comprised of n members such that M(N) = {a(i)} + {b(i)} with b(i) = a(i) + i for i = 1 to n, b(i) is the complementary generated group and a(i) is the complementary generating subgroup.
For G(8) 3 examples are
1{a(i)} = {18,22,20,2,12,4,14,8} and {b(i)} = {19,24,23,6,17,10,21,16}
2{a(i)} = {20,22,14,2,18,4,12,8} and {b(i)} = {21,24,17,6,23,10,19,16}
3{a(i)} = {22,4,16,20,12,2,14,10} and {b(i)} = {23,6,19,24,17,8,21,18}

Note that the ordered groups 1 and 2 are permutations of the same members. Their are no other complementary generating groups for G(8) that yield the complementary group for more than one permutation. An interesting question would be how large must n be for a given group {a(i)} to have x different permutations that each give the complementary group.

An interesting rule would be to for N = 4m + 2 or 4m+3 to make a(1) odd and to make a(i) even for all other a(i) including for all a(i) when N = 4m or 4m+1. For n > 7, this would be the exceptional case rather than the usual case although an example can be found for every n. What is remarkable is that this rule applies even for n = 1 to 5 where there is only one rather than many solutions. It may be informative to find other rules that apply to at least one solution for every n.