Subsets containing Primes

Art of Problem Solving

AoPS Online

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Subsets containing Primes

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2018 AMC 10B #5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1129 posts

#1 h Feb 16, 2018, 5:08 PM • 5 Y

Y by dchen, chessgocube, megarnie, Adventure10, Mango247

How many subsets of $\{2,3,4,5,6,7,8,9\}$ contain at least one prime number?

$\textbf{(A)} \text{ 128} \qquad \textbf{(B)} \text{ 192} \qquad \textbf{(C)} \text{ 224} \qquad \textbf{(D)} \text{ 240} \qquad \textbf{(E)} \text{ 256}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

24 posts

#2 h Feb 16, 2018, 5:09 PM • 3 Y

Y by chessgocube, megarnie, Adventure10

D? Please?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8867 posts

#3 h Feb 16, 2018, 5:09 PM • 3 Y

Y by chessgocube, megarnie, Adventure10

Fairly standard, just $2^8-2^4\implies D$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12 posts

#4 h Feb 16, 2018, 5:18 PM • 4 Y

Y by chessgocube, megarnie, Adventure10, Mango247

Just wondering how did you get 2^8-2^4?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8867 posts

#5 h Feb 16, 2018, 5:19 PM • 4 Y

Y by chessgocube, megarnie, Adventure10, Mango247

mathcount2002 wrote:

Just wondering how did you get 2^8-2^4?

Complimentary counting: count all subsets, then the ones with only composite numbers.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

202 posts

#6 h Feb 16, 2018, 5:20 PM • 4 Y

Y by chessgocube, megarnie, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1491 posts

#7 h Feb 16, 2018, 5:24 PM • 3 Y

Y by chessgocube, megarnie, Adventure10

mathcount2002 wrote:

Just wondering how did you get 2^8-2^4?

To find the number of subsets of a set, you do 2 raised to however many terms in the set there are. So, there are 2^8 = 256 subsets of the original set. Then, we can pick out the numbers that don't have any primes. There are 4 of them. There are 2^4 subsets that don't have a prime number, or 16 subsets without primes. Now, we have 256 - 16 to get 240.

The reason why there are 2^n subsets of n terms is because for each item, you can either include or not include in a subset.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

572 posts

anser

#8 h Feb 16, 2018, 5:34 PM • 4 Y

Y by chessgocube, megarnie, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3789 posts

vsamc

#9 h Apr 10, 2020, 1:44 PM • 3 Y

Y by chessgocube, megarnie, Mango247

lol
I used PIE and symmetry it was bit bashy

mudkipswims solution is much better though

This post has been edited 1 time. Last edited by vsamc, Apr 10, 2020, 1:51 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

416 posts

#10 h Apr 10, 2020, 3:33 PM • 2 Y

Y by chessgocube, megarnie

solution

This post has been edited 1 time. Last edited by EricShi1685, Apr 10, 2020, 3:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1341 posts

#11 h Jun 25, 2021, 6:10 PM • 2 Y

Y by chessgocube, megarnie

solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5606 posts

#12 h Nov 6, 2021, 12:49 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6051 posts

#13 h Sep 3, 2023, 9:21 PM

Y by

Claim: For, a set, with $n,$ elements, the number of subsets, is $2^n.$
Proof 1:
Each, element, can be either, in the set, or out of the set, yielding, $2$ , options, hence, $2^n.$
Proof 2:
Induction. The base case, with $1,$ element obviously holds. Now, if we have a set, with $n,$ elements, and we add another element, we can choose the element, to be used, or to be taken out. In either, case we get $2^n,$ options, hence, $2^n+2^n=2^{n+1}.$
Now, the amount of subsets, using the claim, is $2^8=256.$ Now, the amount of subsets, that contain no prime numbers, is $2^4,$ hence, $2^8-2^4=\boxed{240}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SomeonecoolLovesMaths

3224 posts

SomeonecoolLovesMaths

#14 h Feb 25, 2025, 4:02 PM

Y by

Storage

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a