On a 10-key (0 to 9) keyboard, a 4-digit password has 10^4 possibilities or 10,000. If you have to press four numbers and then enter, you might enter up to 10,000 times.
However, what if you could enter numbers without pressing enter? Then the following sequence:
111122223333
Gets 1 repeat 4, 2 repeat 4, etc. but it also gets 1112, 1122, 1222, etc. etc.
This is my first post on Math Stack and it may be wrong to say this but I'm not necessarily looking for the answer :) Moreso I am asking for suggestions on how to approach this and prove it. Thanks
This is best answered using graph theory, in my opinion.
Let $G$ be a directed graph where the nodes are all possible three-digit codes. For two vertices $u, v$ there is an edge from $u$ to $v$ if the two last digits of $u$ are the two first digits of $v$. That way there are edges from $123$ to each of $231, 232, 233, 234, 235, 236, 237, 238, 239, 230$ and no others.
The nodes each represent the last three button presses. As you press digits on the keypad, you move along the graph. Once you've pressed three buttons for the first time, you have chosen the node corresponding to the three numbers you pressed. For each successive button you press, you move along an edge to the node representing the current three last key presses. That way, each edge represents a specific four-digit code, and each four digit code is represented (for instance, $1234$ is the edge that goes from $123$ to $234$, and $1111$ is the edge that goes form the vertex $111$ and in a loop back to $111$).
This is a so-called De Bruijn graph, and they are well known (and easily checked) to be Eulerian directed graphs. That means that there is a route that goes along each edge exactly once. This corresponds to each code being attempted exactly once, which is clearly as effective as it gets.
This means that the number of required button presses is $3 + 10000$, where the first $3$ are for picking a starting node, and the remaining $10000$ are for testing actual codes, one by one.