What are Subset Pairs as mentioned in this problem?

  • Thread starter 280Z28
  • Start date
In summary, the problem asks for a list of all the subset pairs that can be obtained from a set of n elements.
  • #1
280Z28
5
0
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?
 
Physics news on Phys.org
  • #2
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.
 
  • #3
Which problem is that from?
 
  • #4
mathman said:
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.

Office_Shredder said:
Which problem is that from?

:rolleyes: I posted the links to it right there
 
Last edited:
  • #5
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 24= 16 subsets, there would be 16C2= 16!/(2! 14!)= 8(15)= 120 of those, not 25!
 
  • #6
280Z28 said:
:rolleyes: 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.
 
  • #7
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 :)
 
  • #8
280Z28 said:
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.
 

Related to What are Subset Pairs as mentioned in this problem?

1. What are subset pairs?

Subset pairs are a set of two elements that are both subsets of a larger set. This means that the elements in each pair are a smaller, but still complete, representation of the larger set.

2. How are subset pairs used in this problem?

In this problem, subset pairs are used to show the relationship between different elements in a set. By comparing different subset pairs, we can better understand the structure and patterns within the larger set.

3. How are subset pairs different from regular pairs?

Regular pairs are a set of two distinct elements, while subset pairs are a set of two elements that are both subsets of a larger set. Subset pairs are more specific and have a hierarchical relationship, while regular pairs do not necessarily have any relationship between the two elements.

4. Can a subset pair have more than two elements?

No, a subset pair is specifically defined as a set of two elements. If there are more than two elements, it would be considered a subset combination or a subset group.

5. How can subset pairs be used in scientific research?

Subset pairs can be used in various ways in scientific research. They can help identify patterns and relationships within a data set, aid in data analysis and interpretation, and be used in mathematical and statistical modeling to make predictions and draw conclusions.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Special and General Relativity
2
Replies
51
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
14K
Replies
6
Views
1K
Replies
8
Views
1K
  • Other Physics Topics
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
870
  • Introductory Physics Homework Help
Replies
8
Views
1K
  • Introductory Physics Homework Help
Replies
13
Views
4K
Back
Top