View Full Version: Another math puzzle

Dozensonline > Number Bases > Another math puzzle



Title: Another math puzzle


Dan - March 11, 2007 12:55 AM (GMT)
This was taken from another forum I frequent:

What is the smallest positive integer that cannot be expressed by using the digits 0-9, exactly once each, and the operators + and -? To keep this on-topic, generalize it to the digits 0 to n-1 in base n.

For example, in base 2, we have:

1 = 0+1 = 1+0 = 1-0
2 = 10

And 3 is the smallest positive integer that cannot be expressed.

In base 3,

012 = 5
01+2 = 3
01-2 = -1
0+12 = 5
0+1+2 = 3
0+1-2 = -1
0-12 = -5
0-1+2 = 1
0-1-2 = -3

021 = 7
02+1 = 3
02-1 = 1
0+21 = 7
0+2+1 = 3
0+2-1 = 1
0-21= -7
0-2+1 = -1
0-2-1 = -3

102 = 11
10+2 = 5
10-2 = 1
1+02 = 3
1+0+2 = 3
1+0-2 = -1
1-02 = -1
1-0+2 = 3
1-0-2 = -1

120 = 15
12+0 = 5
12-0 = 5
1+20 = 7
1+2+0 = 3
1+2-0 = 3
1-20 = -5
1-2+0 = -1
1-2-0 = -1

201 = 19
20+1 = 7
20-1 = 5
2+01 = 3
2+0+1 = 3
2+0-1 = -1
2-01 = 1
2-0+1 = 3
2-0-1 = 1

210 = 21
21+0 = 7
21-0 = 7
2+10 = 5
2+1+0 = 3
2+1-0 = 3
2-10 = -1
2-1+0 = 1
21-0 = 7

so 2 is the smallest positive integer that can't be represented.

For larger bases, it's harder to find a brute-force solution because there are n!×3^(n-1) possible ways of arranging the digits and operators.




Hosted for free by InvisionFree