UPDATE (6 June): Several readers have suggested cutting down
the number of keystrokes needed by adding a "yx"
function and/or a ">>1" unary operator. Neither of these will win you the bonus
points. There is a better way.
A good friend of mine, Tamar Ben-Barak, recently phoned me up with a real-world problem: she was in the process of laying down 3 side-by-side paths of stones, each of length n stones, arranged so that the stones form a 3-by-n rectangular lattice. We'll call one end of the ensuing three-stone-wide path its "start" and the other its "end". When walking on the path, one has to move one stone "forward" on each step, but one may begin on any of the three stones on the path's start, may finish on any of the three stones on the path's end, and, when stepping forward, one may move, in addition to the forward step, also one path to the right or to the left. One cannot jump, however, from the left-most path to the right-most one, or vice versa.
The image below gives two examples (one in green, one in blue), of the possible steps that can be taken from particular stones.
Tamar's question was simply this: how many ways, as a function of n, are there, to cross the stone path from start to end? She was in need of an exact, closed form answer to this problem.
For Using your Head is Permitted, I wanted to make the question slightly more complicated. Consider the following pretty-standard-looking pocket calculator.
The functions of this calculator are, I hope, all self-explanatory. On the top, in ochre, are functions for storing and retrieving a number. (The calculator can only store one number in memory.) Below, in white, is a numerical keypad and to its right, in grey, some basic arithmetic operations. Like most calculators of this type, this calculator does not respect arithmetic order: operations are in infix, and are carried out as soon as all operands are entered. Finally, in green at the bottom are some more advanced operations, like exponentiation, incrementation, trigonometric functions and rounding to the nearest integer.
This month's question: if the number n is typed for you on this calculator as the beginning of a computation, what is a calculation that would yield Tamar's desired number in the smallest number of keystrokes? Any solution with 7 or less keystrokes is admissible. Note that you have the option of using the calculator's memory either by storing an intermediate result in it as part of your computation, or by having pre-stored such a result before n is entered. Keystrokes required for such pre-computation are not counted towards your keystroke number, unless the number in memory has to be overwritten as part of the computation. (The idea is to count the number of keystrokes it would take if you had to compute this value for many n values, one after the other.)
As a bonus question, readers are welcomed to think what other standard operators, not appearing in this calculator, would have reduced the number of keystrokes required even further.
List of solvers:Radu-Alexandru Todor (*) (2 June 09:06)
Alexander Ruff (*) (2 June 11:33)
Lorenzo Gianferrari Pini (*) (3 June 01:29)
Oded Margalit (3 June 07:11)
Michael Blaszczyk (4 June 00:03)
Hanlin Ren (4 June 00:07)
Jin Fan (5 June 01:28)
Rui Viana (5 June 06:37)
Harald Bögeholz (5 June 06:59)
Joseph DeVincentis (5 June 10:45)
Itsik Horovitz (*) (7 June 21:19)
Andreas Stiller (*) (8 June 19:46)
Serge Gautier (*) (8 June 19:58)
Zhuo Wang (*) (9 June 08:57)
Daniel Bitin (*) (9 June 23:36)
Yuanming Yu (*) (11 June 09:38)
Claudio Baiocchi (*) (16 June 01:10)
Liu Yi (*) (16 June 13:52)
David L. Dowe (*) (24 June 18:25)
Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.
The solution will be published at the end of the month.
Back to main page