Problem: A safe's circular lock is made up of $100$ keys. To open the safe you need to press $3$ keys. It is known that between $2$ of any of these $3$ keys there are no fewer than $10$ other keys. How many 3-key combinations do you need to try to open the safe if the order in which you press the keys is important?
My solution: We have $100$ options to choose the 1st key. Because we can't use the next $10$ keys on either side of our 1st key (it's a circular lock), we have $100-1-10-10=79$ options for the 2nd key.
My problems: I'm stuck calculating the number of options for the 3rd key. It depends on which key is the second. Suppose we number the keys counterclockwise from $1$ to $100$, where $1$ is our 1st key. If our 2nd choice is $12$, than we have $100-2-10-10-10$ for the 3rd option, but if we choose $50$ as our 2nd choice, than we have $100-2-10*2-10*2$ for our 3rd choice.
What is more, the book says the answer is $469200$ and I'm surprised since $4692/79$ is not an integer number, which (probably) means that the number of options for the 2nd key is not $79$.
Where's the mistake in my reasoning and is the answer $469200$ correct?
Agreed, there are $100$ choices for the first guess, and once that guess is made, regardless of which one, there are $79$ choices for the second guess. However the number of choices for the third guess is not independent of the first two guesses, so the multiplication rule doesn't directly apply to the third guess, which makes the approach problematic.
Instead, the count can be analyzed as follows . . .
Initially, count the number of guess triples, disregarding the order of the key presses.
Define the gap between two guesses as the number of keys strictly between them.
Let the gaps between the guessed numbers, in counterclockwise order, be $$10+a,\,10+b,\,10+c$$ where any cyclic permutation of a gap triple is regarded as an equivalent triple.
Then $a+b+c=67$, so $a,b,c$ can't all be equal.
Consider two cases . . .
Case $(1)$:$\;$Two of $a,b,c$ are equal.
Since we can cyclically permute $(a,b,c)$, we can assume $a$ is the unequal one, and $b=c$.
Then $a$ must be odd, so we can write $a=2a'+1$, for some nonnegative integer $a'$.
Then the equation $a + b + c=67$ reduces to $a'+b=33$.
By the stars-and-bars formula, the number of pairs $(a',b)$ of nonnegative integers satisfying $a'+b=33$ is $$\binom{33 + 2 - 1}{2-1} = 34$$ Alternatively, $b$ can be any integer in the range $0$ to $33$ inclusive, and then the value of $a'$ is forced by $a' = 33-b$, which gives $34$ pairs, matching the stars-and-bars count.
Thus, for case $(1)$, there are $34$ gap triples, up to cyclic equivalence.
For each such triple, we have $100$ choices for the guess which precedes the gap of length $10+a$, so there are $(34)(100)=3400$ guess triples for case $(1)$.
Case $(2)$:$\;$No two of $a,b,c$ are equal.
By the stars-and-bars formula, the number of triples $(a,b,c)$ of nonnegative integers such that $a+b+c=67$ is $$\binom{67 + 3 - 1}{3-1} = \binom{69}{2}=2346$$ but based on the results for case $(1)$, this includes $(3)(34)=102$ triples which have two of $a,b,c$ equal.
Subtracting $102$, the adjusted count is $2346-102=2244$.
But each triple is counted $3$ times (by cyclic equivalence), so the number of gap triples for case $(1)$, up to cyclic equivalence, is $2244/3 = 748$.
Finally, for each such triple, we have $100$ choices for the guess which precedes the gap of whose length is the minimum of $10+a,\,10+b,\,10+c$, so there are $(748)(100)=74800$ guess triples for case $(2)$.
Summing the counts for cases $(1)$ and $(2)$, we get $$74800+3400=78200$$ guess triples, not yet considering the order of the key presses.
Since there are $6$ orders in which the keys could be pressed, there are $$(78200)(6)= 469200$$ guess triples, including the order of the key presses.