Here is a question rather as simple as the boys-and-girls-question (cp. § 302).
It had existed nearly one year in MathOverflow before I answered it under the
pseudonym Hilbert7Problem (which I considered well-received in MathOverflow).
http://mathoverflow.net/questions/103816/bike-lock-puzzle
I was wondering this when using my bike lock, a combination lock with four
dials, each of which has ten digits (0-9) on it in numerical order.
Suppose a bicyclist decides that, from now on, after putting in his combination
on this lock, he will only give the lock one twist to close it. So, he chooses
between 1 and 4 adjacent dials, and rotates them any number of spaces
(other than a multiple of 10, to avoid having the lock end this procedure in
a closed position!)
Unbeknown to the bicyclist, a thief is following him. The thief knows that the
bicyclist uses this procedure to secure his bike. Over a period of days, the
thief notes each combination the lock ends up on. What's the fewest observations
that the thief needs to make before she can deduce the combination
with certainty? What's the fewest observations that she needs to make before
she can reduce it to 10 possibilities? How can a shrewd (but stubborn) bicyclist
maximize the number of observations necessary without repeating a combination?
[Kaveh, 2 Aug 2012]
If you are clever, the thief needs 49 different settings of the dials to know
the correct setting with certainty. This is more than half of all
90 = 4*9 + 3*9 + 2*9 + 1*9 possible settings you can produce (when moving
one dial, two adjacent dials, three adjacent dials, and all four dials,
respectively, into their nine possible incorrect positions).
Let the dials be (a,b,c,d) . Let the correct position be (0,0,0,0) to have
a mental picture. If you put a in eight different positions, say 1, 2, ..., 8,
then the thief does not yet know with certainty the correct one - although she
knows the correct positions 0 of the other three. So if you decided to turn
one or more other dials leaving a at 0 , she would quickly know the complete
correct setting. But if you put (a,b) , (a,b,c) , and (a,b,c,d) also in the
eight different positions avoiding a = 9 , you have 4*8 = 32 positions without
revealing the correct information.
You can do even better, if you choose to start with b. Then you can extend your
number of settings by moving (a,b) , (b,c) , (a,b,c) , (b,c,d) , and (a,b,c,d)
supplying (1+2+2+1)* 8 = 48 settings in total. (Of course the order you choose
does not matter.) You would get the same opportunity with c instead of b .
d however, like a , would supply only 32 possible positions.
The maximum number of different positions, before the thief has discoverd the
correct one, is for n > 2 digits and an even number m of dials:
(n-2)(m/2)(m+2)/ 2 .
For an odd number m of dials you get
(n-2)((m+1)/2)^2 .
Addition: Maximality
If no single dial is moved, we have only 48 settings: 3 pairs, 2 triples
and 1 quadruple in 8 positions each. But if pair (a,b) has been moved twice,
pair (c,d) cannot be moved without revealing the secret. Hence, we get only
40 settings. That is less than the constructed 48. So, in order to maximize
the number of the secret-maintaining settings, we have to move also at least
one single dial. But having moved it twice, we can no longer move any other
single dial or the pair not containing the first. This subtracts 36 from
the 90 possible settings. Since of the remaining 54 settings 6 are always
"the nineth", i.e., revealing the secret, we have at most 48 settings.
[Hilbert7Problem, 25 June 2013]
First Hilbert7Problem was praised: "This is very nice (and much better than what I wrote)" [S. Carnahan]
This answer got six upvotes. Later Hilbert7Problem dared to point out, very politely though, that the "research-professional's" answer to the boys-and-girls-question (cp. § 302 and § 324) shows that at least 100 very stupid users are existing in MathOverflow. Subsequently he was deleted. But my answer to the bike-lock-puzzle remains; only the author has been removed. A copy-right violation.
Regards, WM