What are Subset Pairs as mentioned in this problem?

[280Z28]

What are "Subset Pairs" as mentioned in this problem?

In reference to this problem. BTW - I'm not asking for a solution or even a method of attack for a solution since I just enjoy doing these puzzles. I'm just trying to get clarification on one of the terms used.

http://mathschallenge.net/index.php?section=project&ref=problems&id=106

...out of the 25 possible subset pairs that can be obtained from a set for which n = 4...

Say, for A={3, 5, 6, 7} (example pulled from here), what are the 25 subset pairs?

 

[mathman]

Say, for A={3, 5, 6, 7} (example pulled from here), what are the 25 subset pairs?

Something doesn't look right. There are only six pairs.

 

[Office_Shredder]

Which problem is that from?

 

[280Z28]

Something doesn't look right. There are only six pairs.

I assume it means you can pair a 1 element set with a 1, 2, or 3 element set, but you'd definitely not have to compare 1x1 element sets or nxm element sets where n doesn't equal m. But still, there are (2^4-1) non-empty subsets in that case. :dunno: I just can't find a pairing that counts to 25.

Which problem is that from?

I posted the links to it right there

 

[HallsofIvy]

I think mathman was assuming that "subset pairs" meant "subsets with exactly two members"- there are only 6 of those.

I, on the other hand, assumed it meant "pairs of subsets". Of course, since a 4 element set has 2⁴= 16 subsets, there would be ₁₆C₂= 16!/(2! 14!)= 8(15)= 120 of those, not 25!

 

[shmoe]

I posted the links to it right there

Both your links were to the project euler homepage, not to the specific problem you are looking at, which is possibly 106:

http://mathschallenge.net/index.php?section=project&ref=view&id=106

A subset pair in that problem is a pair of disjoint, non-empty subsets. For your example A={3,5,6,7}. Just sort them by the sizes, for example pairs where both sets have 1 element:

{{3},{5}}, {{3},{6}}, {{3},{7}}, {{5},{6}}, {{5},{7}}, {{6},{7}}

Then look at 2 and 1 elements, 3 and 1 elements, finally 2 and 2 elements.

To count them, count ordered subset pairs instead, then divide by 2. There are 4 ways to pick the first subset to have size 1, then 2^(4-1)-1=7 ways to pick the second set in the pair, so 28 so far. There are 4!/2!/2!=6 ways to pick the first subset to have size 2, 2^(4-2)-1=3 ways to pick the second set, so 18 more. There are 4 ways to pick the first subset to have size 3, and 1 way to pick it's pair, so another 4, for a total of 50. Divide by 2 to kill off our over counting from considering the order as distinct.

 

[280Z28]

Maybe the links are different when you're logged in, but they go to 106 and 103 for me. :dunno:

Thanks for that explanation, I found my error:

What I finally had was:

(4 choose 1)*(3 choose 1) + (4 choose 2)*(2 choose 2) + (4 choose 1)*(3 choose 2) + (4 choose 1)*(3 choose 3)

I forgot to divide the first and second terms by two :)

 

[shmoe]

Maybe the links are different when you're logged in, but they go to 106 and 103 for me. :dunno:

That must be, looking at the url of your links they are slightly different than the one I used. Your version must send you to a default page if you're not signed into that website.