Choosing Subsets Without Consecutive Integers (2006 AMC 12A #25)

Choosing subsets without consecutive integers (in one form or another) is a problem that comes up quite frequently in harder problems. This approach to solving those problems is both simple and useful.

To find a possible subset of {1, 2, 3, ..., x} that does not contain consecutive integers, we can first note that integers of a subset must have a "space" or integer between them. Next, the key to this approach is to think of all x integers in the set as dots. By ordering specific dots in a sequence, we can map the chosen (or red) dots to the chosen integers in the subset.

Now we have that chosen dots are red, so let the "non-chosen" dots be green. But all the orderings include consecutive integers, so we need to remove some "buffer" dots that can later be added between the chosen dots.

So suppose we need to find the total number of 3 integer subsets of {1, 2, 3, ..., 7} such that no two integers are consecutive. Then we have 2 "buffer dots" to be removed, 3 red (chosen) dots, and 2 green (non-chosen) dot. Thus our total would be 5C3 = 5C2 = 10 sequences of dots, each corresponding to a legal subset.

You may be wondering, how can you be sure of the 1-to-1 correlation (or bijection)? Let's look at a sequence: RRGGR. After inserting the "buffer" dots back in right after the R's we get RBRBGGR = {1, 3, 7}. No other sequence of dots can give the same sequence/set because the buffers cannot be replaced by the non-chosen dots. Thus, the buffers do not impact the sequence's "uniqueness"; it only determines which integers are chosen.

[Example 1] Here is a simple example to illustrate the idea: Suppose you have a set S:{1, 2, 3, 4, 5, 6}. We want to find the number of ways to choose a subset of S such that no two consecutive integers are included.

To tackle this problem, we can break it down based on how many integers the subset contains.

First, we have 0 integers, which gives us 6C0 = 1 case.

Then, to choose 1 integer, we have 6C1 = 6 cases.

Now we have 2 integers, which requires 1 buffer dot with 5 remaining dots to choose 2 from. So this equals 5C2 = 10.

Next 3 integer subsets require 2 buffer dots with 4 remaining dots to choose 3 from. This results in 4C3 = 4C1 = 4 possibilities.

Now see that 3 is the maximum number of elements in the set because 4 would not work. Thus our total is 1 + 6 + 10 + 4 = 21 total subsets.

Here is an AMC 12 problem utilizing this idea. This should give you a better idea of how it works. Try it on your own first and then refer to the solution.

[Example 2] 2006 AMC 12A #25: How many non-empty subsets S of {1, 2, 3, ... , 15} have the following properties?

(1) No two consecutive integers belong to S.

(2) If S contains k elements, then S contains no number less than k.

Solution: First we can group our cases by k, which ranges from 1 to 5.

In case 1 (where k = 1) we have the set {1, ..., 15}, so our total is 15C1 = 15.

In case 2 (k = 2) our set becomes {2, ..., 15}. We have 1 buffer dot with 13 remaining dots to choose 2 from, so our total is 13C2 = 78.

In case 3 (k = 3), our set is {3, ..., 15}. With 2 buffers and 11 remaining dots, we see our answer is 11C3 = 165.

In case 4 (k = 4), the set is {4, ..., 15} with 3 buffers. Thus we get 9C4 = 126.

Finally in case 5 (k = 5), we have the set {5, ..., 15} with 4 buffers which results in 7C5 = 7C2 = 21.

Thus our total number is 15 + 78 + 165 + 126 + 21 = 405 total subsets.

Comments

Post a Comment

Popular posts from this blog

Math Formulas + Facts

Sum of cubes and Difference of Cubes a 3  + b 3  = (a + b) (a 2  − a b + b 2  ) a 3  - b 3  = (a - b) (a 2  + a b + b 2  ) Powers to know 5 7  = 78125 5 6  = 15625 5 5  = 3125 Compound Interest A = P(1+r/n) nt Harmonic Series 1+1/2+1/3+1/4+1/5+1/6...+1/n To estimate sum, take the 2 0  term for 1, then take the next 2 1  terms for 2, then take the next  2 2  terms for 3.... Sums: 2 - up to 1/4 2.5 - up to 1/7 3 - up to 1/11 3.5 - up to 1/19 4 - up to 1/31 4.5 - up to 1/51 5 - up to 1/83 Area of Octogon A = 2(1+√2) a 2 Finding the number sides of a regular polygon when you know the interior angle in degrees 180-x° = 360/n Finding total number of diagonals in a polygon n(n-3)/2
Read more

Discovered New Theorem while solving Chinese Remainder Theorem

I was working through some Chinese Remainder Theorem (CRT) problems today (9/24/22), using a new technique introduced in the UKMT Introduction to Number Theory Book. And I noticed a pattern: 9a \equiv 1 \pmod 7 \rightarrow a = 4 7b \equiv 1 \pmod 9 \rightarrow b = 4 Which is cool. But it continues: 7c \equiv 1 \pmod 5 \rightarrow c = 3 5d \equiv 1 \pmod 7 \rightarrow d = 3 And: 35e \equiv 1 \pmod 33 \rightarrow e = 17 33f \equiv 1 \pmod 35 \rightarrow f = 17 Each modular inverse for these pairs were the same! I formed a conjecture, and proved it as a new theorem: Theorem : The solutions a, b to the modular equivalences (n-1)a \equiv 1 \pmod {n+1} (n+1)b \equiv 1 \pmod {n-1} for positive even integers n satisfy a = b = \frac{n}{2}. Update  (12/25/23): More intuitive understanding of Chinese Remainder Theorem (CRT) process. I was looking back at this post, and realized that I had forgotten how the Chinese Remainder Theorem process ...
Read more

Cyclic Quattrocento (Fall 2021 AMC 12B #24)

Image
Fall 2021 AMC 12B #24 Problem:  Triangle ABC has side lengths AB = 11, BC=24, and CA = 20. The bisector of \angle{BAC} intersects \overline{BC} in point D, and intersects the circumcircle of \triangle{ABC} in point E \ne A. The circumcircle of \triangle{BED} intersects the line AB in points B and F \ne B. What is CF? Solution:  We can create a diagram to try to find unique relationships in this problem. By angle chasing in the cyclic quadrilateral ABEC given that AE is the angle bisector of \angle{BAC} we can find that \angle{BAE} = \angle{CAE} = \angle{BCE} = \angle{CBE}. This means that triangle BCE is isosceles and BE = CE, which may be useful later on. Now, we can focus on CF , which is the length we want to find. We can see that ACF has a cevian CB, so we can use Stewart's Theorem (we will "derive" it with the law of cosines here) to solve for CF in terms of other side lengths. We can let \angle{ABC} = \theta which means...
Read more