Combi-natrics!

How many subsets A A of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } \{1,2,3,4,5,6,7,8,9,10\} have the property that no two elements of A A sum to 11 ? 11?


The answer is 243.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Consider the 5 pairs of elements of A A which sum to 11 11 , namely ( 1 , 10 ) , ( 2 , 9 ) , ( 3 , 8 ) , ( 4 , 7 ) (1,10), (2,9), (3,8), (4,7) and ( 5 , 6 ) (5,6) . The desired subsets of A A cannot contain both elements of any of these pairings, but can contain one or the other, or neither, of the elements of each pairing. This leaves us with 3 options for each of the 5 pairings, resulting in a total of 3 5 = 243 3^{5} = \boxed{243} subsets of A A in which no two elements sum to 11 11 .

It should be stated that a "Null" set is considered a set.

Julian Poon - 4 years, 11 months ago

Log in to reply

I think the default is that the null set is a subset of every set unless otherwise indicated.

Brian Charlesworth - 4 years, 11 months ago
Prince Loomba
Nov 1, 2016

We can rephrase the question as selecting 1 1 from each of the following

A) 1 10 ϕ 1|10|\phi

B) 2 9 ϕ 2|9|\phi

C) 3 8 ϕ 3|8|\phi

D) 4 7 ϕ 4|7|\phi

E) 5 6 ϕ 5|6|\phi

Result is 3 3 from each case. Using the fundamental theorem of counting (multiplication), we get the answer as

3 5 = 243 3^{5}=\boxed {243}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...