superprismatic Posted October 14, 2009 Report Share Posted October 14, 2009 I found this puzzle on the ITA Software web site. It is one of ITA's "retired" puzzles. The web site does not give the answer. I suppose the puzzle is difficult enough to require writing a program to solve it. I thought programming this was quite a little tricky but fun as well. I have an answer but bugs have been known to creep into my code. I hope you enjoy it. Here it is: Combining nine 9s with any number of the operators +, -, *, /, (, ) , what is the smallest positive integer that cannot be expressed? Hints: 1)The answer isn't zero. You can express zero like this: (9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9) Also, zero isn't a positive integer. 2)The answer isn't one. You can express one like this: 9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9 3)It's not a trick question. 4)Be sure to handle parentheses correctly. Notes: 1)You cannot exponentiate. 2)You cannot concatenate (for example, put two 9s together to make 99). 3)The - operator can be used in either its binary or unary form. 4)Assume base 10. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 14, 2009 Report Share Posted October 14, 2009 Assuming that when you say "smallest" you mean on a linear scale then (9*9*9*9*9*9)*(9-9-9) would yield something close to the correct answer. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted October 14, 2009 Author Report Share Posted October 14, 2009 (edited) Assuming that when you say "smallest" you mean on a linear scale then (9*9*9*9*9*9)*(9-9-9) would yield something close to the correct answer. That's negative. The object is to find the smallest positive integer which cannot be expressed. Edited October 14, 2009 by superprismatic Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 14, 2009 Report Share Posted October 14, 2009 (edited) Thanks a bundle, SP, especially since I am just going to bed. My immediate and obvious answer must be incorrect, and so I must think of something subtler. Edited October 14, 2009 by jerbil Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 14, 2009 Report Share Posted October 14, 2009 2 =((9+9)/9+(9+9)/9)/((9+9)/9) 3 =((9+9+9)/9+(9-9)/9)+((9-9)/9) 4 =(9+9)/9+(9+9)/9-(9-9)/9 5 =((9+9+9)/9+(9+9)/9)+((9-9)/9) 6 =((9+9)/9+(9+9)/9)+((9+9)/9) 7 =((9*9)/9-(9+9)/9)+((9-9)/9) 8 =((9+9)/9*(9+9)/9)*(9+9)/9 9 =9+9+9+9+9-9-9-9-9 10 =9*9/9+9/9+(9-9)/9 11 =((9*9)/9+(9+9)/9)-((9-9)/9) 12 =9*9/9+9/9+(9+9)/9 13 =9*9/9+(9+9)/9+(9+9)/9 14 =9*9/9+(9+9+9+9+9)/9 15 =-(9+9+9)/9+9+9+(9-9)/9 16 =((9*9*9)/(9*9)-(9+9)/9)+9 17 =-(9+9)/9+9+9+(9-9+9)/9 18 =9+9-9/9+9/9+9/9-9/9 19 =9+9+(9+9)/9-9/9+9-9 20 =((9*9*9)/(9*9)+(9+9)/9)+9 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 14, 2009 Report Share Posted October 14, 2009 I'm trying to write a program for this one. At the moment its looking like 4 billion combinations. Most of these will be repeated combinations but I haven't found a way eliminate that yet. It's looking like it will take several minutes of processing time at best. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 15, 2009 Report Share Posted October 15, 2009 195.. used a C code Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 15, 2009 Report Share Posted October 15, 2009 195.. used a C code I seriously think I could do better than that, but I cannot find a proof of a minimum, as yet. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted October 15, 2009 Author Report Share Posted October 15, 2009 195.. used a C code No, that's not it. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 16, 2009 Report Share Posted October 16, 2009 (edited) My answer is 41 but I think that's just because there are tricks to manipulating the 9's that I haven't been able to figure out. Any help? Edited October 16, 2009 by Tuckleton Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted October 16, 2009 Author Report Share Posted October 16, 2009 My answer is 41 but I think that's just because there are tricks to manipulating the 9's that I haven't been able to figure out. Any help? 41 = (((9+9+9)*(9+9+9))+9)/(9+9) Quote Link to comment Share on other sites More sharing options...
0 Guest Posted October 16, 2009 Report Share Posted October 16, 2009 Aha! Many thanks. Back to work! Quote Link to comment Share on other sites More sharing options...
Question
superprismatic
I found this puzzle on the ITA
Software web site. It is one of
ITA's "retired" puzzles. The
web site does not give the answer.
I suppose the puzzle is difficult
enough to require writing a program
to solve it. I thought programming
this was quite a little tricky but
fun as well. I have an answer but
bugs have been known to creep into
my code. I hope you enjoy it.
Here it is:
Combining nine 9s with any number of
the operators +, -, *, /, (, ) , what
is the smallest positive integer that
cannot be expressed?
Hints:
1)The answer isn't zero. You can
express zero like this:
(9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9)
Also, zero isn't a positive integer.
2)The answer isn't one. You can
express one like this:
9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9
3)It's not a trick question.
4)Be sure to handle parentheses
correctly.
Notes:
1)You cannot exponentiate.
2)You cannot concatenate (for example,
put two 9s together to make 99).
3)The - operator can be used in either
its binary or unary form.
4)Assume base 10.
Link to comment
Share on other sites
11 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.