A calculator has only 3 buttons. The first multiplies the current value by 3, the second adds 2 and the third subtracts 2. Starting with 0 what is the least number of presses you need to reach 100?
Answer
Seven keystrokes. The sequence of numbers is
0, 2, 4, 12, 36, 34, 102, 100
Proof that this is the only solution in seven or fewer steps:
The question is the same as "A calculator has three buttons: add 2, subtract 2, and divide an integer by 3. How many steps do you need to get from 100 to 0?". The first steps must be to add or subtract 2 until a multiple of 3 is reached. Clearly the first such multiple should be stopped at for a division, as proceeding to add or subtract further will take more steps than doing so after the division. So we're at 102 after one step or 96 after two steps. We divide, and are at 34 after two steps or 32 after three. We repeat the addition/subtraction step and are at 36 after three steps, 30 after four, or 36 after five (but can reject the latter as nonoptimal). We divide again and are at 12 after four steps or 10 after five. We add/subtract again if needed, and are at 12 after four steps, 12 after five (reject as nonoptimal), or 6 after seven. We divide again and are at 4 after five steps or 2 after eight. We add/subtract again and are at 6 after six steps, 0 after seven, 6 after ten (reject), or 0 after nine (reject). Further steps won't get us to 0 in seven steps, so we're done.
No comments:
Post a Comment