2018 AMC 12A Problem #12

Let S S be a set of 6 integers taken from { 1 , 2 , , 12 } \{1,2,\dots,12\} with the property that if a a and b b are elements of S S with a < b , a < b, then b b is not a multiple of a . a. What is the least possible value of an element in S S ?


Next problem

Previous problem

All problems

7 2 4 5 3

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

Giorgos K.
Mar 30, 2018

Mathematica code

Select[Subsets[Range@12,{6}],!Or@@(IntegerQ[#2/#]&@@#&/@Subsets[#,{2}])&]

returns all the S S sets

{4, 5, 6, 7, 9, 11}, {4, 6, 7, 9, 10, 11}, {5, 6, 7, 8, 9, 11}, {5, 7, 8, 9, 11, 12}, {6, 7, 8, 9, 10, 11}, {7, 8, 9, 10, 11, 12}

So the answer is 4 4

Zain Majumder
Feb 11, 2018

Trial and error is the fastest way to solve this. When choosing numbers to add to the set, we must go from largest to smallest when possible. For example, realize that choosing 4 4 would eliminate 2 2 other integers ( 8 8 and 12 12 ), but choosing 12 12 only eliminates 4 4 , making it a better option in general.

If 3 3 was in the set, we find that 11 , 10 , 8 , 11, 10, 8, and 7 7 can be added into the set, but no more. Therefore 3 3 does not work. We can find a valid set S S if 4 \boxed{4} is the lowest integer: { 4 , 6 , 7 , 9 , 10 , 11 } \{4, 6, 7, 9, 10, 11\} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...