Difference between revisions of "2023 AIME I Problems/Problem 11"
Mathboy100 (talk | contribs) |
Mathboy100 (talk | contribs) |
||
Line 1: | Line 1: | ||
− | Unofficial problem statement: Let <math>S</math> be the set <math>\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}</math>. How many subsets of <math>S</math> have exactly one pair of consecutive elements? (Ex: <math> | + | Unofficial problem statement: Let <math>S</math> be the set <math>\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}</math>. How many subsets of <math>S</math> have exactly one pair of consecutive elements? (Ex: <math>\{1, 2, 6, 10\}</math>) |
==Solution== | ==Solution== |
Revision as of 12:49, 8 February 2023
Unofficial problem statement: Let be the set
. How many subsets of
have exactly one pair of consecutive elements? (Ex:
)
Solution
Define to be the number of subsets of
that have
consecutive element pairs, and
to be the number of subsets that have
consecutive pair.
Using casework on where the consecutive pair is, it is easy to see that .
We see that ,
, and
. This is because if the element
is included in our subset, then there are
possibilities, and otherwise there are
possibilities. Thus, by induction,
is the
th Fibonacci number.
This means that .
~mathboy100