Wednesday 2 September 2015

mathematics - Three button calculator part 2


A calculator only has 3 buttons. The first multiplies the current value by 3, the second adds 2 and the third subtracts 2. The calculator always starts with 0. What is the smallest positive even number that requires at least 10 button presses to make?



Here is the first version of the puzzle: Three button calculator



Answer



The smallest number is:



244



Proof:



Let's work backwards. Instead of reaching the number starting at 0, we reduce the number to 0 by undoing the steps, i.e. by adding/subtracting 2 or dividing by 3.

The following statements are true:
Any even number 2 or less can be reduced to 0 in at most 1 step.

Any even number 8 or less can be reduced to 0 in at most 3 steps.
Any even number 26 or less can be reduced to 0 in at most 5 steps.
Any even number 80 or less can be reduced to 0 in at most 7 steps.
Any even number 242 or less can be reduced to 0 in at most 9 steps.

The first statement is trivially true. Each following statement is easy to check given the previous one. For example, given any number of 242 or less, it is either a multiple of 3 or else you can add/subtract 2 to make it so. You can then divide it by 3. In this way you will have reduced it to an even number of 80 or less using at most 2 steps.

So the first even number for which 10 steps might be necessary is 244. It can be done in 10 steps in any of the ways going left to right in this diagram:


 244-246- 82-84-28-30-10-12-4
\ \ \ \ \
242-240-80-78-26-24- 8-6-2-0


244 cannot be done in fewer steps because any alternative route will go to the left in the diagram, or takes an even longer off-piste route involving 3 consecutive additions/subtractions to go from one multiple of three to another.

No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...