wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> IBM Research: November 2006 Puzzle
        
(Message started by: Sameer on Nov 10th, 2006, 2:06pm)
Title: IBM Research: November 2006 Puzzle
Post by Sameer on Nov 10th, 2006, 2:06pm
Consider arithmetic expressions formed from the integers 1,2,3,4 (each of which is to 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.

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.

Note: You are allowed to reuse operators (1+2+3+4). You are not allowed to join digits together (12+34). / (divide) is not one of the allowed operators.

Source: http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/November2006.html
Title: Re: IBM Research: November 2006 Puzzle
Post by irrational on Nov 17th, 2006, 2:21pm
Damn... I found this so interesting I wanted to post it too  :)..

Observations:
The maximum number that can be reached is:
(4*3*2)+1 = 25
4*3*(2+1) = 36

[EDIT]
I jsut relaized I cannot reuse the operators. The maximum then would be (I think):
(4*(3+2))-1 = 19
[/EDIT]

I am writing a computer simulation for this. Will post the results as soon as I finish.

For part 1:
I am thinking of a FSM with 1,2,3,4 as the states and the +,-,* as transitions.
and bruteforce generation from 1 - 25 :)

It might be easier to test each number by hand though :)
Title: Re: IBM Research: November 2006 Puzzle
Post by rmsgrey on Nov 17th, 2006, 3:07pm

on 11/17/06 at 14:21:31, irrational wrote:
Damn... I found this so interesting I wanted to post it too  :)..

Observations:
The maximum number that can be reached is (4*3*2)+1 = 25 (add 1 since 1 is the multiplicative identity)

[EDIT]
I jsut relaized I cannot reuse the operators. The maximum then would be (I think):
(4*(3+2))-1 = 19
[/EDIT]

I am writing a computer simulation for this. Will post the results as soon as I finish.

For part 1:
I am thinking of a FSM with 1,2,3,4 as the states and the +,-,* as transitions.
and bruteforce generation from 1 - 25 :)

It might be easier to test each number by hand though :)

1) The original post says you are allowed to re-use operators.
2) Re-using operators, I can get several values above 25.
Title: Re: IBM Research: November 2006 Puzzle
Post by Sameer on Nov 17th, 2006, 3:15pm
Hmmm how can you get values above 25? i wonder if they intended the use of "**" or something like that...  my answer was actually [hide]26[/hide] unless you have something else.. i don't have a proper approach to it though...
Title: Re: IBM Research: November 2006 Puzzle
Post by rmsgrey on Nov 17th, 2006, 3:30pm
I suspect it may not be possible to get 26, but I haven't put much work in.

I believe the highest representable value is 36 which can be represented as (2+1)*3*4
Title: Re: IBM Research: November 2006 Puzzle
Post by Sameer on Nov 17th, 2006, 4:27pm
Ok, I didn't think we could use brackets.. in that case 26 is not the lowest.. because (4*3+1)*2 = 26 .. I think the answer in that case is 29...
Title: Re: IBM Research: November 2006 Puzzle
Post by Icarus on Nov 17th, 2006, 8:16pm

on 11/17/06 at 16:27:34, Sameer wrote:
Ok, I didn't think we could use brackets..



on 11/10/06 at 14:06:12, Sameer wrote:
For example 1 = (2*3)-(4+1) so 1 can represented.


::)
Title: Re: IBM Research: November 2006 Puzzle
Post by Sameer on Nov 17th, 2006, 9:58pm

on 11/17/06 at 20:16:15, Icarus wrote:
::)


Like I mentioned in previous thread, I can't read!!  :P. Now I can't even understand my own post!!
Title: Re: IBM Research: November 2006 Puzzle
Post by irrational on Nov 18th, 2006, 6:40am
Damn my eyes...

I read can reuse as cannot reuse ::)

reedited the above post again ;D
 
Title: Re: IBM Research: November 2006 Puzzle
Post by irrational on Nov 18th, 2006, 6:47am
Damn Sameer beat me to the post again..

Do you ever sleep ;)

[hide]29[/hide] is what I got too...
Title: Re: IBM Research: November 2006 Puzzle
Post by Sameer on Nov 18th, 2006, 6:18pm

on 11/18/06 at 06:47:23, irrational wrote:
Damn Sameer beat me to the post again..

Do you ever sleep ;)

[hide]29[/hide] is what I got too...


Actually it was just 8pm my time when I posted it!!
:)
Title: Re: IBM Research: November 2006 Puzzle
Post by Margit on Nov 22nd, 2006, 1:31am
Ahh, 27 and 28 are also possible.
I believe 29 is the answer.
29 is prime therefore we have to add/subtract some number to get this and it is not possible with the remaining digits to get anywhere near.
Title: Re: IBM Research: November 2006 Puzzle
Post by Margit on Nov 22nd, 2006, 8:01am
For the second part, I thought that
[hide] 1 2 4 7 [/hide] looked promising.
But stuck at [hide] 38 [/hide] with these numbers.
Title: Re: IBM Research: November 2006 Puzzle
Post by pex on Nov 22nd, 2006, 11:29am

on 11/22/06 at 08:01:39, Margit wrote:
For the second part, I thought that
[hide] 1 2 4 7 [/hide] looked promising.
But stuck at [hide] 38 [/hide] with these numbers.


How about
[hideb]
1 = (1 + 2 + 5) / 8
2 = 1 + 8 - 2 - 5
3 = (2 - 1) * (8 - 5)
4 = 2 * (1 + 5) - 8
5 = 1 * (2 + 8 - 5)
6 = 1 + 2 + 8 - 5
7 = 2 * (8 - 5) + 1
8 = 2 * (1 + 8 - 5)
9 = (1 + 2) * (8 - 5)
10 = 1 + 5 + 8 / 2
11 = 1 * (2 * 8 - 5)
12 = 1 + 5 + 8 - 2
13 = (1 + 8) * 2 - 5
14 = 2 + 5 + 8 - 1
15 = 1 * (2 + 5 + 8)
16 = 1 + 2 + 5 + 8
17 = 2 * 5 + 8 - 1
18 = 1 * (2 * 5 + 8)
19 = 2 * 5 + 1 + 8
20 = 1 * 5 * 8 / 2
21 = 1 * (2 * 8 + 5)
22 = 2 * 8 + 1 + 5
23 = 5 * (1 + 2) + 8
24 = (5 - 1) * (8 - 2)
25 = 8 * (5 - 2) + 1
26 = 1 * 2 * (5 + 8)
27 = 2 * (5 + 8) + 1
28 = 8 * (1 + 5 / 2)
29 = 8 * (1 + 2) + 5
30 = 1 * 5 * (8 - 2)
31 = 5 * (8 - 2) + 1
32 = 8 * (1 + 5 - 2)
33 = 5 * (8 - 1) - 2
34 = 8 * (5 - 1) + 2
35 = 5 * (1 + 8 - 2)
36 = (1 + 5) * (8 - 2)
37 = 5 * (8 - 1) + 2
38 = 1 * (5 * 8 - 2)
39 = (1 + 2) * (5 + 8)
40 = 5 * 8 * (2 - 1)
41 = 5 * 8 + 2 - 1
42 = 1 * (5 * 8 + 2)
43 = 5 * 8 + 1 + 2
44 = 8 * (5 + 1 / 2)
45 = 5 * (2 + 8 - 1)
46 = 8 * (1 + 5) - 2
47 = 5 * (1 + 8) + 2
48 = 8 * (2 + 5 - 1)
49 = (2 + 5) * (8 - 1)
50 = 1 * 5 * (2 + 8)
51 = 5 * (2 + 8) + 1
52 = not representable
[/hideb]
Title: Re: IBM Research: November 2006 Puzzle
Post by Sameer on Nov 22nd, 2006, 11:34am
pex, division is not allowed.
Title: Re: IBM Research: November 2006 Puzzle
Post by pex on Nov 22nd, 2006, 11:41am

on 11/22/06 at 11:34:16, Sameer wrote:
pex, division is not allowed.



I'll join the list of people who cannot read...  :-[
Title: Re: IBM Research: November 2006 Puzzle
Post by irrational on Nov 22nd, 2006, 11:42am
Wouldn't there be multiple answers to the part b of the question.

I am not saying they would be infinite but there definitely should be a nice number of them :)
Title: Re: IBM Research: November 2006 Puzzle
Post by pex on Nov 22nd, 2006, 12:04pm

on 11/22/06 at 11:34:16, Sameer wrote:
pex, division is not allowed.


Then maybe
[hideb]
1 = 1 * (2 + 5 - 6)
2 = 1 + 2 + 5 - 6
3 = 2 * (6 - 5) + 1
4 = 1 + 2 + 6 - 5
5 = 2 * 5 + 1 - 6
6 = 2 * (1 + 5) - 6
7 = 1 * (2 * 6 - 5)
8 = 2 * 6 + 1 - 5
9 = 5 * (1 + 2) - 6
10 = 1 + 5 + 6 - 2
11 = (2 - 1) * (5 + 6)
12 = 2 + 5 + 6 - 1
13 = 1 * (2 + 5 + 6)
14 = 1 + 2 + 5 + 6
15 = (6 - 1) * (5 - 2)
16 = 1 * (2 * 5 + 6)
17 = 2 * 5 + 1 + 6
18 = 2 * 6 + 1 + 5
19 = 6 * (5 - 2) + 1
20 = 1 * 5 * (6 - 2)
21 = 5 * (1 + 2) + 6
22 = 1 * 2 * (5 + 6)
23 = 2 * (5 + 6) + 1
24 = 6 * (1 + 5 - 2)
25 = 5 * (1 + 6 - 2)
26 = 6 * (5 - 1) + 2
27 = 5 * (6 - 1) + 2
28 = 1 * (5 * 6 - 2)
29 = 5 * 6 + 1 - 2
30 = 5 * 6 * (2 - 1)
31 = 5 * 6 + 2 - 1
32 = 1 * (5 * 6 + 2)
33 = (1 + 2) * (5 + 6)
34 = 6 * (1 + 5) - 2
35 = 5 * (2 + 6 - 1)
36 = 6 * (2 + 5 - 1)
37 = 5 * (1 + 6) + 2
38 = 6 * (1 + 5) + 2
39 = 5 * (2 + 6) - 1
40 = 1 * 5 * (2 + 6)
41 = 5 * (2 + 6) + 1
42 = 1 * 6 * (2 + 5)
43 = 6 * (2 + 5) + 1
44 = not representable
[/hideb]
Title: Re: IBM Research: November 2006 Puzzle
Post by Sameer on Nov 22nd, 2006, 5:50pm
How about 37 using 1,2,3 and 5.
Title: Re: IBM Research: November 2006 Puzzle
Post by Sir Col on Nov 26th, 2006, 1:27pm
Nice work, pex. I found your solution and I found that [hide]1258[/hide] also gave [hide]43[/hide] consecutive solutions using an exhaustive search.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board