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 11: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
