MathDB

25

Part of 2006 AMC 12/AHSME

Problems(2)

Counting subsets

Source: AMC 12 2006A, Problem 25

2/5/2006
How many non-empty subsets S S of {1,2,3,…,15} \{1, 2, 3, \ldots, 15\} have the following two properties? (1) No two consecutive integers belong to S S. (2) If S S contains k k elements, then S S contains no number less than k k. <spanclass=′latex−bold′>(A)</span>277<spanclass=′latex−bold′>(B)</span>311<spanclass=′latex−bold′>(C)</span>376<spanclass=′latex−bold′>(D)</span>377<spanclass=′latex−bold′>(E)</span>405 <span class='latex-bold'>(A) </span> 277\qquad <span class='latex-bold'>(B) </span> 311\qquad <span class='latex-bold'>(C) </span> 376\qquad <span class='latex-bold'>(D) </span> 377\qquad <span class='latex-bold'>(E) </span> 405
countingdistinguishabilityprobabilitybinomial coefficientsAMC
Sequence

Source: AMC 12 2006B, Problem 25

2/17/2006
A sequence a1,a2,… a_1, a_2, \ldots of non-negative integers is defined by the rule a_{n \plus{} 2} \equal{} |a_{n \plus{} 1} \minus{} a_n| for n≥1 n\ge 1. If a_1 \equal{} 999, a_2 < 999, and a_{2006} \equal{} 1, how many different values of a2 a_2 are possible? <spanclass=′latex−bold′>(A)</span>165<spanclass=′latex−bold′>(B)</span>324<spanclass=′latex−bold′>(C)</span>495<spanclass=′latex−bold′>(D)</span>499<spanclass=′latex−bold′>(E)</span>660 <span class='latex-bold'>(A) </span> 165 \qquad <span class='latex-bold'>(B) </span> 324 \qquad <span class='latex-bold'>(C) </span> 495 \qquad <span class='latex-bold'>(D) </span> 499 \qquad <span class='latex-bold'>(E) </span> 660
algorithmnumber theorygreatest common divisorEulerfunctionEuclidean algorithmrelatively prime