Using your Head is Permitted

November 2008 riddle

This month's riddle is a variation over the riddle-theme of "given the numbers 1, 6, 7 and 9 and the four basic arithmetic operations, reach 23". I never liked this genre of riddles very much, due to the incredibly large number of possibilities to try out. In my variation, I have therefore tried to restrict the number of possibilities to as few as possible. For this month's riddle, you will need to use only the number 1 (using the "1" as a digit, for example in "11" or "111" is not allowed), and only two operations: addition and multiplication.

Given enough 1's, any natural can be represented. For example, 7 can be represented as a summation of seven 1's: 1+1+1+1+1+1+1=7. However, there is a "cheaper" representation, using less 1's: 7=1+(1+1)*(1+1+1). Here, only six 1's were used.

This month's riddle pertains to the function N(), where N(x) is the minimum number of 1's required to represent the natural x. You are required to provide a function M() that approximates N() in the following sense:

  1. For any x, M(x)≤N(x)
  2. For any x, N(x)<1.6M(x)
  3. There exists an infinite number of values, x, for which M(x)=N(x)
M() should be a monotone increasing function (in the narrow sense), mapping from the naturals to the reals, unlike N(), which maps to the naturals and is not monotone. M() should be formulated explicitly (non-recursively) and in an easy-to-calculate manner.

To be on the solvers' list, find M() and prove that it satisfies the three conditions given above.

List of solvers:

Dan Dima (1 November 06:22)
Sen Gu (1 November 06:32)
Li Wei (1 November 08:22)
Yingjie Xu (1 November 09:44)
Hongcheng Zhu (1 November 13:43)
Albert Stadler (4 November 20:58)
Gaoyuan Chen (5 November 01:03)
Marcos Simões (5 November 11:28)
Itsik Horovitz (5 November 21:31)
Omer Angel (6 November 03:49)
Bojan Bašić (6 November 23:10)
Xiaohui Bei (11 November 18:47)

Elegant solutions can be submitted to the puzzlemaster at 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.


To solution

Back to main page