Problem 106

[D_R_Eadful]

I wonder, how the example numbers of subset pairs were obtained? For example, 25 for n=4.

Thanks.

[GraemeMcRae]

EDIT -- Originally, I said the strings had to have at least one 0 and at least one 1, which was wrong (as pointed out below). I corrected that statement here:

I made a list of ternary strings of length 4 that have at least one 1 and at least one 2, and whose first nonzero digit is 1. There are 25 such strings: 1200, 1210, 1020, 0120, 1120, 1220, 1201, 1211, 1021, 0121, 1121, 1221, 1002, 0102, 1102, 1202, 0012, 1012, 0112, 1112, 1212, 1022, 0122, 1122, 1222. There are 966 such strings of length 7: 1200000, 1210000, 1020000, 0120000, 1120000, 1220000, 1201000, 1211000, 1021000, 0121000, 1121000, 1221000, 1002000, 0102000, 1102000, 1202000, 0012000, 1012000, 0112000, 1112000, ..., 1001222, 0101222, 1101222, 1201222, 0011222, 1011222, 0111222, 1111222, 1211222, 1021222, 0121222, 1121222, 1221222, 1002222, 0102222, 1102222, 1202222, 0012222, 1012222, 0112222, 1112222, 1212222, 1022222, 0122222, 1122222, 1222222.

[neonash7777]

Assume the first digit has to be one.
Leaving us 3 spots where one has to be 1 and one has to be 0.
The last spot then can be 2,1,0 ...we'll say X

So 3! yields 6 combinations, 01X, 0X1,10X, 1X0, X01, and X10
Since the X can be three things that makes 18 combinations

Now we can have a starting 0 or 00 or 000 starting as long as 1 follows
01XX (9 more possibilities)
or
001X (3 more)
or
0001 (1 more)

So 18+9+3+1=31 Combinations

I don't see where the 25 comes from assuming I followed your rules...

[GraemeMcRae]

Oops! I "misspoke". I should have said every string must have at least one "1" and one "2", and its first nonzero digit is "1".

[rayfil]

For n=4, the 25 possible subset pairings are (the examples based on set A{1,2,3,4}):

a) 6 pairings of subsets containing one element with subsets containing one element, (Ex: B{1} and C{2}
b) 12 pairings of subsets containing one element with subsets containing two elements, (Ex: B{1} and C{2,3}
c) 4 pairings of subsets containing one element with subsets containing three elements, (Ex: B{1} and C{2,3,4}
d) 3 pairings of subsets containing two elements with subsets containing two elements, (Ex: B{1,2} and C{3,4}

[GraemeMcRae]

That's a good way to express it, rayfil. Adopting your terminology, for n=7, the 966 possible subset pairings are (the examples based on set A{1,2,3,4,5,6,7}):

a) 21 pairings of subsets containing one element with subsets containing one element, e.g. B{1} and C{2}
b) 105 pairings of subsets containing two elements with subsets containing one element, e.g. B{1,2} and C{3}
c) 140 pairings of subsets containing three elements with subsets containing one element, e.g. B{1,2,3} and C{4}
d) 105 pairings of subsets containing four elements with subsets containing one element, e.g. B{1,2,3,4} and C{5}
e) 42 pairings of subsets containing five elements with subsets containing one element, e.g. B{1,2,3,4,5} and C{6}
f) 7 pairings of subsets containing six elements with subsets containing one element, e.g. B{1,2,3,4,5,6} and C{7}
g) 105 pairings of subsets containing two elements with subsets containing two elements, e.g. B{1,2} and C{3,4}
h) 210 pairings of subsets containing three elements with subsets containing two elements, e.g. B{1,2,3} and C{4,5}
i) 105 pairings of subsets containing four elements with subsets containing two elements, e.g. B{1,2,3,4} and C{5,6}
j) 21 pairings of subsets containing five elements with subsets containing two elements, e.g. B{1,2,3,4,5} and C{6,7}
k) 70 pairings of subsets containing three elements with subsets containing three elements, e.g. B{1,2,3} and C{4,5,6}
l) 35 pairings of subsets containing four elements with subsets containing three elements, e.g. B{1,2,3,4} and C{5,6,7}

[zeycus]

I solved problem 106 some days ago, and the interesting is that I felt that what I was calculating is not what is actually required. I calculated the number of inequialities that may not hold. For example, there are 70 for n = 7, as is stated. However, I don't think it would be necessary to check them all in order to guarantee that the set is a special sum set, surely some of them imply the rest. Or am I wrong? Has someone given some thought to this point already?

[daniel.is.fischer]

Well, given any particular set (of large enough size, must be larger than four), there are some subset pairs B, C , where you can deduce e.g. s(B) < s(C) from the results of the comparisons of other subsets, e.g. if you compare B = {a₁, a₅} with C = {a₂, a₄}, then if s(B) < s(C) you needn't compare B with {a₃, a₄} and if s(B) > s(C), you needn't compare B with {a₂, a₃}, but I'm fairly sure that you can't find a size n and a general pair of subsets (let the elements be a₁ < a₂ < ... < a_n-1 < a_n and the subsets be given by the sets of indices) where you cannot deduce s(B) [ne] s(C) by the indices alone (hence this pair belongs to the class whose size is asked), but you can deduce s(B) [ne] s(C) from s(D) [ne] s(E) for all {D,E} belonging to this class except {B,C}.

[zeycus]

Thank you for the answer, surely you are right. However I am not still completely satisfied. For example, with n=5, there are exactly 5 pairs (B,C) such that S(B) != S(C) is not implied. Two of them are (B={a₁, a₄}, C = {a₂,a₃}) and (B={a₁, a₅}, C = {a₂,a₃}). If for the first pair we would check S(C) < S(B), then there would be no need to check the second inequality. So, sometimes we can make sure that the set is indeed a special sum set, checking less than 5 cases. But you are right, It works sometimes, not always.

[daniel.is.fischer]

One can always omit some checks based on the outcome of the comparison of other pairs, I gave an example. But which checks can be omitted depends on whether the result is '<' or '>' (and if the first check returns '=', all other comparisons are superfluous).
And, what should be taken into account is that the problem text goes "For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?", so the strategy does not involve determining whether s(B) < s(C) or s(B) > s(C), but only whether s(B) = s(C). Then, although I have no formal proof (yet), I believe no checks can be omitted and you did indeed calculate what was required.
However, although this is the literal interpretation of the problem text, your understanding is quite natural, too.
Maybe we should make that clearer.

[zeycus]

Of course you are right, literally I agree. On the other hand, to check whether S(B) = S(C), you calculate both and so you know if it is < or >. But I agree with you, that is now what the problem talks about. Thank you for the answer.

[daniel.is.fischer]

On the other hand, to check whether S(B) = S(C), you calculate both and so you know if it is < or >.

But of course you let your computer do the check and you wrote !=, <> or /= in your code

[daniel.is.fischer]

Okay, I have filled in the details of my proof idea, that was less fussy than I feared.
Unfortunately the proof would give away too much about the solution of this problem to post it here.
So just the statement (hope the denotations are clear):
For any size n and any interesting pair of index sets I,J, there is a set A of positive integers such that A satisfies condition ii and (A_I,A_J) is the only interesting subset pair with equal sum.

[zeycus]

Then, there is nothing more to discuss, you were completely right. Thanks a lot for the effort you made to clarify this point!

[daniel.is.fischer]

You're welcome. It was interesting to go in deep. When I solved that problem, I stopped at counting the pairs which were not obviously having different sums.

[relue]

Problem 106 says: "Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4".

I can't see where this 25 is coming from. For n=4, there are 6 different subsets of size 2, which gives 15 different subset pairs. There are 4 different subsets of size 3, which gives 6 different subset pairs. 15+6=21. Where are the other 4 possible subset pairs coming from?

[daniel.is.fischer]

Sizes No of pairs
1-1    6
1-2   12
1-3    4
2-2    3

Total: 6+12+4+3 = 25
The subsets have to be disjoint, but need not have the same size.

[relue]

"Disjoint" is the key word that I miss. Thanks.

How do I remove this thread?

[btilly]

In the problem description, what are "subset pairs" and how are they being counted?

In the description it says that with n=4 there are 25 subset pairs. From the description it would seem that they are talking about pairs of non-empty disjoint subsets. But there are 9 of those:

• {1}, {2}
• {1}, {3}
• {1}, {4}
• {2}, {3}
• {2}, {4}
• {3}, {4}
• {1,2}, {3,4}
• {1,3}, {2,4}
• {1,4}, {2,3}

I've tried various variations of ordered vs unordered pairs, disjoint and non-disjoint, including the empty set or not, and I don't come out to 25 subset pairs.

Could someone clarify what is meant by "subset pairs" and where the 25 number comes from?

[hk]

What makes you think the subsets need to have equal cardinality when counting up to 25?