Author |
Topic: IBM Research: November 2006 Puzzle (Read 810 times) |
|
Sameer
Uberpuzzler
Pie = pi * e
Gender: 
Posts: 1261
|
 |
IBM Research: November 2006 Puzzle
« on: Nov 10th, 2006, 2:06pm » |
 Quote  Modify
|
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/November2 006.html
|
|
 IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
irrational
Junior Member
Gender:
Posts: 52
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #1 on: Nov 17th, 2006, 2:21pm » |
Quote Modify
|
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
|
| « Last Edit: Nov 18th, 2006, 6:44am by irrational » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #2 on: Nov 17th, 2006, 3:07pm » |
Quote Modify
|
on Nov 17th, 2006, 2:21pm, 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.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #3 on: Nov 17th, 2006, 3:15pm » |
Quote Modify
|
Hmmm how can you get values above 25? i wonder if they intended the use of "**" or something like that... my answer was actually 26 unless you have something else.. i don't have a proper approach to it though...
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #4 on: Nov 17th, 2006, 3:30pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #5 on: Nov 17th, 2006, 4:27pm » |
Quote Modify
|
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...
|
| « Last Edit: Nov 17th, 2006, 4:32pm by Sameer » |
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #6 on: Nov 17th, 2006, 8:16pm » |
Quote Modify
|
on Nov 17th, 2006, 4:27pm, Sameer wrote:| Ok, I didn't think we could use brackets.. |
|
on Nov 10th, 2006, 2:06pm, Sameer wrote:| For example 1 = (2*3)-(4+1) so 1 can represented. |
|
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #7 on: Nov 17th, 2006, 9:58pm » |
Quote Modify
|
on Nov 17th, 2006, 8:16pm, Icarus wrote:
Like I mentioned in previous thread, I can't read!!  . Now I can't even understand my own post!!
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
irrational
Junior Member
Gender:
Posts: 52
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #8 on: Nov 18th, 2006, 6:40am » |
Quote Modify
|
Damn my eyes...
I read can reuse as cannot reuse
reedited the above post again 
|
|
IP Logged |
|
|
|
irrational
Junior Member
Gender:
Posts: 52
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #9 on: Nov 18th, 2006, 6:47am » |
Quote Modify
|
Damn Sameer beat me to the post again..
Do you ever sleep 
29 is what I got too...
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #10 on: Nov 18th, 2006, 6:18pm » |
Quote Modify
|
on Nov 18th, 2006, 6:47am, irrational wrote:Damn Sameer beat me to the post again..
Do you ever sleep
29 is what I got too... |
|
Actually it was just 8pm my time when I posted it!!
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Margit
Junior Member
Gender: 
Posts: 54
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #11 on: Nov 22nd, 2006, 1:31am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 22nd, 2006, 5:02am by Margit » |
IP Logged |
|
|
|
Margit
Junior Member
Gender:
Posts: 54
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #12 on: Nov 22nd, 2006, 8:01am » |
Quote Modify
|
For the second part, I thought that
1 2 4 7 looked promising.
But stuck at 38 with these numbers.
|
| « Last Edit: Nov 22nd, 2006, 8:07am by Margit » |
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #13 on: Nov 22nd, 2006, 11:29am » |
Quote Modify
|
on Nov 22nd, 2006, 8:01am, Margit wrote:For the second part, I thought that
1 2 4 7 looked promising.
But stuck at 38 with these numbers. |
|
How about
| hidden: |
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
|
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #14 on: Nov 22nd, 2006, 11:34am » |
Quote Modify
|
pex, division is not allowed.
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #15 on: Nov 22nd, 2006, 11:41am » |
Quote Modify
|
on Nov 22nd, 2006, 11:34am, Sameer wrote:| pex, division is not allowed. |
|
I'll join the list of people who cannot read... 
|
|
IP Logged |
|
|
|
irrational
Junior Member
Gender:
Posts: 52
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #16 on: Nov 22nd, 2006, 11:42am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #17 on: Nov 22nd, 2006, 12:04pm » |
Quote Modify
|
on Nov 22nd, 2006, 11:34am, Sameer wrote:| pex, division is not allowed. |
|
Then maybe
| hidden: |
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
|
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #18 on: Nov 22nd, 2006, 5:50pm » |
Quote Modify
|
How about 37 using 1,2,3 and 5.
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: IBM Research: November 2006 Puzzle
« Reply #19 on: Nov 26th, 2006, 1:27pm » |
Quote Modify
|
Nice work, pex. I found your solution and I found that 1258 also gave 43 consecutive solutions using an exhaustive search.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print