Arithmetic Expressions

I chose this problem from Ponder This to illustrate some ideas about combinatorics and binary trees. It goes like this:

Consider arithmetic expressions formed from the integers $1,2,3,4$ (each of which is to be used exactly once) and the operators +,-,* (addition, subtraction, multiplication). We will ask about the values that can be represented by such expressions. For example $1 = (2*3)-(4+1)$ so 1 can represented. Note $1 = (2+3)-4$ would not be a valid representation because it does not use 1. You are allowed to reuse operators $(1+2+3+4).$ You are not allowed to join digits together $(12+34).$

For this month’s puzzle we ask two questions:

What is the smallest positive integer that can not be represented by such expressions involving 1,2,3,4?

Find a set of 4 distinct positive integers $a,b,c,d$ such that the smallest positive integer that can not be represented by such expressions involving $a,b,c,d$ (instead of $1,2,3,4$ ) is greater than the answer to part 1. You may wish to use a computer for this part.

An arithmetic operation can be seen as a binary tree: The leaves are the numbers, and the nodes are the operators. In our case, we only need four leaves and three nodes. Note the three different examples below, with the four digits $1,2,3,4$ in the same order, but with different operations in between.

The reader will surely have no trouble realizing that any possible arithmetic operation that we can construct with the constraints of this problem, is going to be a full binary tree with four leaves. The term full means that every node other than the leaves has two children. There are only five possible trees with this property:

Take the first of those trees for example: we can code it as $(s_1\oplus_1 (s_2 \oplus_2 (s_3 \oplus_3 s_4))),$ where $s_k$ symbolizes any of the possible numbers $(1, 2, 3, 4),$ and $\oplus_k$ symbolizes any of the three allowed operations. A basic application of combinatorics tells us that, for any of the trees above, there will be 648 different ways to combine those digits and operations: four possibilities for $s_1$ , three possibilities for $s_2$ , two possibilities for $s_3$ (and this fixes the digit in $s_4$ ), and of course, three possibilities for each $\oplus_k$ . There are then 3240 outcomes, many of which are of course equal.

This can very well be the strategy for a brute-force approach to solving the first part of the puzzle: The following sage script codes each possible full binary tree as a string with variables, and then we run loops on each variable to obtain all possible results. A posterior sorting and elimination of repeated values does the trick:

digits=[1,2,3,4]
strings=['(%d%s(%d%s(%d%s%d)))', '%d%s((%d%s%d)%s%d)', 
         '(%d%s%d)%s(%d%s%d)', '(%d%s(%d%s%d))%s%d',
         '((%d%s%d)%s%d)%s%d']
opps=['+','-','*'] 
output={}
for opp1 in opps:
    for opp2 in opps:
        for opp3 in opps:
            for s in permutations(digits):
                a,b,c,d=s
                for str in strings:
                    output[eval(str%(a,opp1,b,opp2,c,opp3,d))]=
                           str%(a,opp1,b,opp2,c,opp3,d)
for k in uniq(output):
    print &quot;%6d=%s&quot;%(k,output[k])

-23=1-((4*3)*2)

-22=(2*(1-(4*3)))

-21=(3*(1-(4*2)))

-20=(4*(1-(3*2)))

-19=(1-(4*(3+2)))

-18=(3*2)*(1-4)

-17=(1-(3*(4+2)))

-16=(4*2)*(1-3)

-15=3*((1-4)-2)

-14=(2-(4*(3+1)))

-13=(1-(4*3))-2

-12=(4*3)*(1-2)

-11=(3*(1-4))-2

-10=(2*1)-(4*3)

 -9=3*((2-4)-1)

 -8=4*((2-3)-1)

 -7=(4*(1-2))-3

 -6=3*((2*1)-4)

 -5=(3*1)-(4*2)

 -4=4*((2*1)-3)

 -3=(3*(2-(4-1)))

 -2=2*((3*1)-4)

-1=((4*1)-3)-2

 0=4*((3-2)-1)

 1=(4*(2-1))-3

 2=((3*2)*1)-4

 3=(4*(3-2))-1

 4=4*((3*1)-2)

 5=((4*2)*1)-3

 6=3*((4*1)-2)

 7=(3*(4-1))-2

 8=(4*(3-(2-1)))

 9=((4*3)-2)-1

10=((4*3)*1)-2

11=((4*2)*1)+3

12=(4*3)*(2-1)

13=(4*3)-(1-2)

14=((4*3)*1)+2

15=(3*(4-(1-2)))

16=(4*2)*(3-1)

17=(3*(4+2))-1

18=(3*2)*(4-1)

19=(4*(3+2))-1

20=4*((3*2)-1)

21=3*((4*2)-1)

22=2*((4*3)-1)

23=((4*3)*2)-1

24=((4*3)*2)*1

25=((4*3)*2)+1

26=2*((4*3)+1)

27=3*((4*2)+1)

28=4*((3*2)+1)

30=(3*2)*(4+1)

32=(4*2)*(3+1)

36=(4*3)*(2+1)

The smallest positive integer not representable in this fashion is 29.

To look for a set of four digits solving the second part of the puzzle, simply change the call of digits in the first line of the script, and run it again. One that worked for me was the set $\{2,3,4,5\}:$ the smallest positive integer not representable for this set of digits is 32. Can you find a set of four digits that gives as a result anything less than 32 and larger than 29?

References

Programming Python (See all Computer Programmer Books)

Comments (1) Trackbacks (0) Leave a comment Trackback

srockets (@srockets)

May 26, 2014 at 7:07 am

Reply

A shorter code that doesn’t use eval(): https://gist.github.com/shayel/2397850f9b2c3df7e3aa

No trackbacks yet.

Francisco Blanco-Silva