Problem 106

[btilly]

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

The fact that we're only asked about the first rule, which only applies to subsets of equal size.

Judging from that you seem to be counting "disjoint pairs of non-empty subsets". (Checks all 3 numbers.) Yup. You are. And I found the 70 of size 7.

I think I see how to do it for 12 though I probably won't code it until after my hand heals.

[daniel.is.fischer]

What happened to your hand?

[btilly]

What happened to your hand?

I was playing volleyball, two of us went for a spike receive, my fingers bent backwards and I broke the bone right under my ring finger on my right hand.

I'll be in a cast until at least Jan 8, and will be very busy after that. In the meantime I am trying to type one-handed.

[daniel.is.fischer]

Ouch. That hurts. Best wishes for a quick healing.

[btilly]

Thanks. It will be fine, it is just a pain.

[Babamots]

I had a tough time understanding what was meant by "need to be tested." I'd appreciate it if someone would correct me if I'm wrong:

When the problem refers to subsets that "need to be tested for equality," it means pairs of subsets that COULD have equal sums without breaking prior conditions (condition ii. and strictly increasing elements) and therefore must be tested.

In particular, when n=4 and the set is {a,b,c,d} we only need to check whether S({a,d}) = S({b,c}) since:

• Disjoint sets of unequal size have different sums (condition ii.).
  Disjoint sets of size 1 have one element each and the elements are distinct (strictly increasing elements).
  The only disjoint sets of size 2 are {a,b},{c,d} and {a,d},{b,c}. It is not possible that S({a,b}) = S({c,d}) since a<c, b<d (and consequently S({a,b}) < S({c,d}) ), so the only thing we need to test is S({a,d}) = S({b,c}).

[jaap]

I had a tough time understanding what was meant by "need to be tested." I'd appreciate it if someone would correct me if I'm wrong:

That's correct, though you did overlook disjoint sets {a,c},{b,d}, for which you can deduce that they cannot possibly be equal and so also need not be tested.

[ignat_s]

I was having really hard time understanding where 25 comes from. (Now I understand what you guys meant.) I found out an interesting fact: the function discussed (let's denote it a(n), so that a(4)=25, a(7)=966, and a(12)=261625 ) turns out to be exactly the Stirling numbers of the second kind S(n+1,3). I.e. a(4) = S(5,3) counts the number of ways to split a set of 5 elements into 3 disjoint nonempty subsets:

[ [ 1 ], [ 2 ], [ 3, 4, 5 ] ],
[ [ 1 ], [ 2, 3 ], [ 4, 5 ] ],
[ [ 1 ], [ 2, 3, 4 ], [ 5 ] ],
[ [ 1 ], [ 2, 3, 5 ], [ 4 ] ],
[ [ 1 ], [ 2, 4 ], [ 3, 5 ] ],
[ [ 1 ], [ 2, 4, 5 ], [ 3 ] ],
[ [ 1 ], [ 2, 5 ], [ 3, 4 ] ],
[ [ 1, 2 ], [ 3 ], [ 4, 5 ] ],
[ [ 1, 2 ], [ 3, 4 ], [ 5 ] ],
[ [ 1, 2 ], [ 3, 5 ], [ 4 ] ],
[ [ 1, 2, 3 ], [ 4 ], [ 5 ] ],
[ [ 1, 2, 4 ], [ 3 ], [ 5 ] ],
[ [ 1, 2, 5 ], [ 3 ], [ 4 ] ],
[ [ 1, 3 ], [ 2 ], [ 4, 5 ] ],
[ [ 1, 3 ], [ 2, 4 ], [ 5 ] ],
[ [ 1, 3 ], [ 2, 5 ], [ 4 ] ],
[ [ 1, 3, 4 ], [ 2 ], [ 5 ] ],
[ [ 1, 3, 5 ], [ 2 ], [ 4 ] ],
[ [ 1, 4 ], [ 2 ], [ 3, 5 ] ],
[ [ 1, 4 ], [ 2, 3 ], [ 5 ] ],
[ [ 1, 4 ], [ 2, 5 ], [ 3 ] ],
[ [ 1, 4, 5 ], [ 2 ], [ 3 ] ],
[ [ 1, 5 ], [ 2 ], [ 3, 4 ] ],
[ [ 1, 5 ], [ 2, 3 ], [ 4 ] ],
[ [ 1, 5 ], [ 2, 4 ], [ 3 ] ]

The part containing the element 'n+1' (i.e. '5' above) can be omitted, and the resulting list will be exactly the set of all pairs of disjoint subsets of 1...n.

[hk]

Ah well, the number of possible subset pairs it given anyway.

[larryleinweber]

Problem 103, 105 and 106 each begin by stating "Let S(A) represent the sum of elements in set A of size n." The problems indicate that elements can be summed and compared and examples are provided, but it never stated that the elements are numbers. Problem 103 states "If S(A) is minimised for a given n, we shall call it an optimum special sum set," but does not state that the numbers must be positive, and integers, except by example. Problem 106 states that "we shall assume that a given set contains n strictly increasing elements," although the elements of a set have no order. The wanted term is "sequence." The ultimate clarification, unfortunately, is that without these inferences, the official correct result cannot be obtained. Is there an FAQ anywhere that states the apparent default assumption that everything is a positive integer?

[Guvante]

Problem 103, 105 and 106 each begin by stating "Let S(A) represent the sum of elements in set A of size n." The problems indicate that elements can be summed and compared and examples are provided, but it never stated that the elements are numbers. Problem 103 states "If S(A) is minimised for a given n, we shall call it an optimum special sum set," but does not state that the numbers must be positive, and integers, except by example. Problem 106 states that "we shall assume that a given set contains n strictly increasing elements," although the elements of a set have no order. The wanted term is "sequence." The ultimate clarification, unfortunately, is that without these inferences, the official correct result cannot be obtained. Is there an FAQ anywhere that states the apparent default assumption that everything is a positive integer?

You cannot have any negative or zero integers while satisfying the second condition. Given the set of 4 -1, b, c, d for some 0 < b < c < d we can trivially break it using -1 + b < c when any subset of size 2 must be larger than any element. Similarly for all negative numbers a < b < c < d < 0 implies a + b < c. Finally 0 < b < c < d has 0 + b < c.

[jneb]

[quote="ignat_s"]the function discussed (...) turns out to be exactly the [***] numbers.

Please don't do that. You spoil the fun for others.

[jimfan]

I cannot explain why... This question appears to be a riddle more than a mathematics / programming challenge...

[RishadanPort]

I just want 1 clarification.

The elements of the set dont have to be whole numbers?

Its a bit confusing as the other questions have only integers.

[hk]

I just want 1 clarification.

The elements of the set dont have to be whole numbers?

Its a bit confusing as the other questions have only integers.

No they're integers.

[kkm000]

No they're integers.

hk, I assumed that they were natural numbers, not integers. If they aren't, then this problem is not related to the problem 103, because, if we assume ℤ and not ℕ in the problem 103, then an SSS with a minimal sum either does not exist (i.e., you can always find one with a more negative sum than a given one), or smaller for an SSS being subset of ℤ than that of ℕ. My solution checked out, so I assume than the minimal-sum SSS in the problem 103 is a subset of ℕ. So, please clarify,

(a) Are they integers or natural number for the problem 106?
(b) Are they integers or natural number for the problem 103?

Thanks for the clarification!

[hk]

Please consider the consequences of the second condition.

[kkm000]

Please consider the consequences of the second condition.

True. Thanks.

[hamsterofdeath]

Hi, I'm totally lost on this one.
I have a set of numbers of size 4.
According to my Java knowledge, sets don't allow duplicates nor do they have an order, but in this thread here people were talking about sets like '1222' (as an example for a 4 element set)

So my first question is: what are valid sets for 106, and which sets aren't valid?

Thrn, how can there be 25 possible pairs of subsets?
Because I count:
1,2 ,3,4,12,13,14,23,24,34,123,124,234,134 which is 14, not 25.

And what does it mean when rule 1 doesn't need to be checked? When is it necessary, why isn't it always necessary?

[DJohn]

1222 is mentioned in one post, as part of a reply to someone asking how to obtain the number of pairs of subsets. It is not a set, or an element of a set, but part of one method of enumerating subset pairs.

If we have a set with four elements A = { a, b, c, d } and we want to find all of the subsets of it, one way we can do this is by writing all 16 four-digit strings of 0 and 1: 0000, 0001, 0010, 0011, ..., 1111. Each digit corresponds to an element of A. If it is 1, we include that element in this subset. If it is 0, we don't. That gives us the 16 subsets {}, {a}, {b}, {a, b}, ..., {a, b, c, d}.

For this problem, we want pairs of disjoint subsets. We can do this by writing four-digit strings of 0, 1, and 2. If a digit is 1, that element goes in one subset. If it is 2, it goes in the other. If it is 0, it goes in neither. The subsets are non-empty, so we must have at least one 1 and one 2 in the string. Finally, we want the first non-zero digit to be 1 to avoid double-counting: the pair {a,b} and {c,d} is the same as the pair {c,d} and {a,b}, and we only want to count it once. Under those conditions, you will find that there are 25 possible strings, and so there are 25 subset pairs.

That's only one method of enumerating subset pairs. Nothing in the problem statement requires that you use it. It's just an easy way (for people who are used to this sort of method) of seeing that there are 25 subset pairs for a 4 element set.


For your second question: This method requires some way of mapping positions in the string to elements of the set. It gives them an order that the set itself doesn't have. If you make that order "increasing numerically" (so elements corresponding to earlier digits in the string are less than later digits), then for some pairs you know in advance that the sums can't be equal. In my example above, since a < b < c < d, it is impossible for a+b = c+d. We don't need to check equality for that subset pair. But for {a,d} and {b,c}, we do need to check, because the answer depends on the particular values of the elements of A: if A is {1, 2, 3, 4} then 1+4 = 2+3. But if A was {1, 2, 3, 5}, 1+5 /= 2+3.