Discussion:
An amusing problem
(too old to reply)
Peter Percival
2016-12-02 14:23:51 UTC
Permalink
Raw Message
I was going to post this to alt.algebra.math, but it seems to be dead or
infected with solution manual peddlars. Actually, it is a family of
problems -

Consider the digits 123456789 in that order. Distribute addition and
subtraction signs among them so that the sum 100 results.

12 + 3 - 4 + 5 + 67 + 8 + 9

is one solution, there are others.

This problem is in Knuth's taocp vol 4A, but I can't find the specific
page right now.

He asks what is the least sum (i.e. in place of 100) for which one can
do this? Suppose it's m. And I ask -

What is the algorithm that works generally for sums
m, m+1, m+2, ..., 123456789? I.e., a partition is
produced or "no solution exists" is reported.
--
Do, as a concession to my poor wits, Lord Darlington, just explain
to me what you really mean.
I think I had better not, Duchess. Nowadays to be intelligible is
to be found out. -- Oscar Wilde, Lady Windermere's Fan
Peter Percival
2016-12-02 14:34:51 UTC
Permalink
Raw Message
Post by Peter Percival
I was going to post this to alt.algebra.math, but it seems to be dead or
infected with solution manual peddlars. Actually, it is a family of
problems -
Consider the digits 123456789 in that order. Distribute addition and
subtraction signs among them so that the sum 100 results.
12 + 3 - 4 + 5 + 67 + 8 + 9
is one solution, there are others.
This problem is in Knuth's taocp vol 4A, but I can't find the specific
page right now.
He asks what is the least sum (i.e. in place of 100) for which one can
do this?
Of course he doesn't! He asks for the least +ve integer *not*
representable in this way. See Ex 111 on page 319. The soln is on page
702 where the problem is attributed to Dudeney in 1899.
Post by Peter Percival
Suppose it's m. And I ask -
What is the algorithm that works generally for sums
m, m+1, m+2, ..., 123456789? I.e., a partition is
produced or "no solution exists" is reported.
Omit m.
--
Do, as a concession to my poor wits, Lord Darlington, just explain
to me what you really mean.
I think I had better not, Duchess. Nowadays to be intelligible is
to be found out. -- Oscar Wilde, Lady Windermere's Fan
James Waldby
2016-12-05 22:40:41 UTC
Permalink
Raw Message
...
Post by Peter Percival
Consider the digits 123456789 in that order. Distribute addition and
subtraction signs among them so that the sum 100 results.
12 + 3 - 4 + 5 + 67 + 8 + 9
is one solution, there are others.
This problem is in Knuth's taocp vol 4A [...] He asks [...]
[...] for the least +ve integer *not* representable
in this way. See Ex 111 on page 319. The soln is on page
702 where the problem is attributed to Dudeney in 1899.
Post by Peter Percival
Suppose it's m. And I ask -
What is the algorithm that works generally for sums
m, m+1, m+2, ..., 123456789? I.e., a partition is
produced or "no solution exists" is reported.
Omit m.
I don't know of an efficient general algorithm for this, but maybe
a divide-and-conquer method could reduce the asymptotic run time
somewhat compared to the exponential time that enumerating all
combinations requires. A time savings comes from being able to
process parts in linear order or via tree search or via a heap.

Dividing up the problem is easy for combinations that have a plus
or minus operator at the divide point, but is clumsy when numbers
cross that point. One approach is to store each segment value in
two parts, eg for a left half store the instance's value up to the
last operator in it, and store the last (not-necessarily-complete)
number value as well.

Note, the problem at hand is so small that it takes only some dozens
of milliseconds to list all combinations. See python program below.
From its output one can see 211 as an answer to Knuth's exercise.

By modifying its output, sorting, filtering, etc, one can see that
the sums 1, 15, and 21 can be represented in 43 ways; the sum 27 in
44 ways; and the sum 9 in 46 ways, some of them being +1+2+3+4-5-6-7+8+9
+1+2+3-4+5-6+7-8+9 +1+2-3-4-56+78-9 +1+23-45+6+7+8+9 -1-23+45-6-7-8+9
+1-23+4+5-67+89 etc.

#!/usr/bin/env python
# Ref: Subject: An amusing problem From: Peter Percival
# Date: Fri, 2 Dec 2016 14:23:51 sci.math,alt.math.recreational
vals, pow8, digis = [], 81*81, range(9,0,-1)
for offset in [0, 2*pow8]:
for base in xrange(0,pow8):
ops = top = offset + base
num = total = 0
rad = 1;
way = ''
for dig in digis:
num += rad*dig
way += chr(ord('0')+dig)
rad *= 10
op = (top%3)-1
top /= 3
if op:
total += op*num
way += '+' if op>0 else '-'
num = 0
rad = 1
vals.append((total,''.join(reversed(way))))
vals = sorted(vals)
k = 0
while k < len(vals):
v = vals[k][0]
n = 0
print v, ':',
while k < len(vals) and vals[k][0]==v:
print vals[k][1], # comment out to not see the ways
k += 1; n += 1
print ' :', n
--
jiw
Nick
2016-12-07 10:35:09 UTC
Permalink
Raw Message
Post by James Waldby
...
Post by Peter Percival
Consider the digits 123456789 in that order. Distribute addition and
subtraction signs among them so that the sum 100 results.
12 + 3 - 4 + 5 + 67 + 8 + 9
is one solution, there are others.
This problem is in Knuth's taocp vol 4A [...] He asks [...]
[...] for the least +ve integer *not* representable
in this way. See Ex 111 on page 319. The soln is on page
702 where the problem is attributed to Dudeney in 1899.
Post by Peter Percival
Suppose it's m. And I ask -
What is the algorithm that works generally for sums
m, m+1, m+2, ..., 123456789? I.e., a partition is
Omit m.
I don't know of an efficient general algorithm for this, but maybe
a divide-and-conquer method could reduce the asymptotic run time
somewhat compared to the exponential time that enumerating all
combinations requires. A time savings comes from being able to
process parts in linear order or via tree search or via a heap.
Dividing up the problem is easy for combinations that have a plus
or minus operator at the divide point, but is clumsy when numbers
cross that point. One approach is to store each segment value in
two parts, eg for a left half store the instance's value up to the
last operator in it, and store the last (not-necessarily-complete)
number value as well.
I don't understand this comment. For me it seems we have the set of
digits plus a choice of three operators (+,-,string concatenation). A
prefix operator only has 2 choices. So total choices are in python
2*(3**8). So we would essentially have a ternary search tree. You seem
to have recognised this in the python program.

I once went to a talk given by Martin Fowler who is very famous in
software development for discussing patterns and techniques for
efficiently designing quality software. Whilst I appreciated the quality
and significance of his work I always found it very boring and difficult
to follow.

So anyway he starts the talk by describing how when he was young,
learning software development, he found Knuth very boring and hard
going. At that point, always having loved Knuth, I understood we were
clearly just very different types of people.

If you too love Knuth I would recommend

<https://www.amazon.co.uk/Artificial-Intelligence-Approach-Stuart-Russell/dp/1292024208>

Very much in the spirit of Knuth and it describes practical ways to
solve this sort of problem. This type of problem would normally involve
applying a few rules to identify potential solution areas and then
applying search trees. A simple type of rule might be that a solution
cannot more that 5 digits in a number.
James Waldby
2016-12-08 09:51:53 UTC
Permalink
Raw Message
Post by Nick
Post by James Waldby
...
Post by Peter Percival
Consider the digits 123456789 in that order. Distribute addition and
subtraction signs among them so that the sum 100 results.
12 + 3 - 4 + 5 + 67 + 8 + 9
is one solution, there are others.
This problem is in Knuth's taocp vol 4A [...] He asks [...]
[...] for the least +ve integer *not* representable
in this way. See Ex 111 on page 319. The soln is on page
702 where the problem is attributed to Dudeney in 1899.
Post by Peter Percival
Suppose it's m. And I ask -
What is the algorithm that works generally for sums
m, m+1, m+2, ..., 123456789? I.e., a partition is
Omit m.
I don't know of an efficient general algorithm for this, but maybe
a divide-and-conquer method could reduce the asymptotic run time
somewhat compared to the exponential time that enumerating all
combinations requires. A time savings comes from being able to
process parts in linear order or via tree search or via a heap.
Dividing up the problem is easy for combinations that have a plus
or minus operator at the divide point, but is clumsy when numbers
cross that point. One approach is to store each segment value in
two parts, eg for a left half store the instance's value up to the
last operator in it, and store the last (not-necessarily-complete)
number value as well.
I don't understand this comment. For me it seems we have the set of
digits plus a choice of three operators (+,-,string concatenation). A
prefix operator only has 2 choices. So total choices are in python
2*(3**8). So we would essentially have a ternary search tree. You seem
to have recognised this in the python program.
Yes, one approach is to use a ternary search tree. My Python program
didn't generate the tree per se, but instead decoded numbers into
ternary digits, representing subtraction, concatenation, and addition.

Generating a tree more explicitly might allow use of higher-power
search techniques, like alpha-beta pruning.

Regarding my comment about storing segment values in two parts:
Suppose the digit string is a little larger, eg 50 instead of 9.
Generating and/or searching a tree may become impractical. A
divide-and-conquer method should develop lists of possible values
for sections of the digit string and allow combining those values
efficiently. For an oversimplified example, if there are n = m+m
digits and if our target is t and if left and right lists have
sorted values, we process the left list in order and the right list
in reverse order at the same time, advancing the left list pointer
when left+right < t, and reducing the right list pointer when
t < left+right, thus taking time O(m) + O(G) where O(G) is time to
generate a list over m characters. But along with individual values
in the list, we presumably need number-part values, and in general
don't have useful limits on their lengths.

[snip: interesting comments on Martin Fowler re Knuth]
Post by Nick
If you too love Knuth I would recommend
<https://www.amazon.co.uk/Artificial-Intelligence-Approach-Stuart-Russell/dp/1292024208>
Very much in the spirit of Knuth and it describes practical ways to
solve this sort of problem. This type of problem would normally involve
applying a few rules to identify potential solution areas and then
applying search trees. A simple type of rule might be that a solution
cannot more that 5 digits in a number.
When the target has lots of digits, a rule like that may be
difficult to prove correct.
--
jiw
Nick
2016-12-09 00:11:02 UTC
Permalink
Raw Message
Post by James Waldby
Post by Nick
Post by James Waldby
...
Post by Peter Percival
Consider the digits 123456789 in that order. Distribute addition and
subtraction signs among them so that the sum 100 results.
12 + 3 - 4 + 5 + 67 + 8 + 9
is one solution, there are others.
This problem is in Knuth's taocp vol 4A [...] He asks [...]
[...] for the least +ve integer *not* representable
in this way. See Ex 111 on page 319. The soln is on page
702 where the problem is attributed to Dudeney in 1899.
Post by Peter Percival
Suppose it's m. And I ask -
What is the algorithm that works generally for sums
m, m+1, m+2, ..., 123456789? I.e., a partition is
Omit m.
I don't know of an efficient general algorithm for this, but maybe
a divide-and-conquer method could reduce the asymptotic run time
somewhat compared to the exponential time that enumerating all
combinations requires. A time savings comes from being able to
process parts in linear order or via tree search or via a heap.
Dividing up the problem is easy for combinations that have a plus
or minus operator at the divide point, but is clumsy when numbers
cross that point. One approach is to store each segment value in
two parts, eg for a left half store the instance's value up to the
last operator in it, and store the last (not-necessarily-complete)
number value as well.
I don't understand this comment. For me it seems we have the set of
digits plus a choice of three operators (+,-,string concatenation). A
prefix operator only has 2 choices. So total choices are in python
2*(3**8). So we would essentially have a ternary search tree. You seem
to have recognised this in the python program.
Yes, one approach is to use a ternary search tree. My Python program
didn't generate the tree per se, but instead decoded numbers into
ternary digits, representing subtraction, concatenation, and addition.
Generating a tree more explicitly might allow use of higher-power
search techniques, like alpha-beta pruning.
Suppose the digit string is a little larger, eg 50 instead of 9.
Generating and/or searching a tree may become impractical. A
divide-and-conquer method should develop lists of possible values
for sections of the digit string and allow combining those values
efficiently. For an oversimplified example, if there are n = m+m
digits and if our target is t and if left and right lists have
sorted values, we process the left list in order and the right list
in reverse order at the same time, advancing the left list pointer
when left+right < t, and reducing the right list pointer when
t < left+right, thus taking time O(m) + O(G) where O(G) is time to
generate a list over m characters. But along with individual values
in the list, we presumably need number-part values, and in general
don't have useful limits on their lengths.
I'm still not sure I'm getting you but it is easy to see how this type
of idea could develop a recursive program. Basically build a set of all
solutions for n digits and the add digit n+1. There is the added
complexity you need to remember all potential last terms in the n case
so you can append another digit. Possibly it has slightly lower
complexity that ternary exponential. I was going to test it then it
occurred to me that there are only 9 possibly ten digits.

Anyway FWIW please excuse my Python. I'm more C#, Java, VBA orientated

#main function to solve the problem
def find_lowest_sum_not_ok():
digits=9
set_of_sums = find_all_sums_from_digits(digits)
print( "Potential Complexity guess (ordinality({(sums,last_term)})="
+ str( len(set_of_sums)))
res = get_first(set_of_sums)
print( "Lowest Solution " + str(res ))
return res

#finds the firrst gap in the set of posible sum tuples
# {(sum,last term)}
def get_first(nums):
last = 0
# unpack tuples (sum,last item) to give a sorted list of sums > 0
sorted_sums_only = sorted({ x[0] for x in nums if x[0] > 0 })
for key in sorted_sums_only:
if key - last != 1:
return (last + 1)
last = key

#returns a set of tuples containing potential sums and the
# last term in the sum.
#max_digit == number of digits
def find_all_sums_from_digits(digits) :
res = set()

#base case
if digits==1:
res.add((-1,-1))
res.add((1,1))
return res

#recursive step
for (t,l) in find_all_sums_from_digits(digits-1):
# +
res.add((t + digits, digits))
# -
res.add((t - digits, -digits))
# concatenate digits
if l>0:
e = l * 10 + digits
else:
e = l * 10 - digits
res.add((t - l + e, e))
return res
Post by James Waldby
[snip: interesting comments on Martin Fowler re Knuth]
Post by Nick
If you too love Knuth I would recommend
<https://www.amazon.co.uk/Artificial-Intelligence-Approach-Stuart-Russell/dp/1292024208>
Very much in the spirit of Knuth and it describes practical ways to
solve this sort of problem. This type of problem would normally involve
applying a few rules to identify potential solution areas and then
applying search trees. A simple type of rule might be that a solution
cannot more that 5 digits in a number.
When the target has lots of digits, a rule like that may be
difficult to prove correct.
Not really it is easy to see it must be less than half the digits.
James Waldby
2016-12-09 03:15:34 UTC
Permalink
Raw Message
Post by Nick
Post by James Waldby
Post by Nick
...
Post by Peter Percival
Consider the digits 123456789 in that order. Distribute addition and
subtraction signs among them so that the sum 100 results.
12 + 3 - 4 + 5 + 67 + 8 + 9
is one solution, there are others.
[big snip, separately replied to]
Post by Nick
Post by James Waldby
Post by Nick
This type of problem would normally involve
applying a few rules to identify potential solution areas
and then applying search trees. A simple type of rule
might be that a solution cannot more than 5 digits in a number.
When the target has lots of digits, a rule like that may be
difficult to prove correct.
Not really it is easy to see it must be less than half the digits.
Applying that rule when the target sum is, for example, 234567
or 456789 would result in missing out on solutions +1+234567+8-9
and -1+234567-8+9 for the one and +1+2-3+456789 -1-2+3+456789
for the other. Less trivially, suppose the digit list is as
follows: (3,4,4,9,4,2,9,5,8,4,0,3,1,7,8,4,1,2,7,4,4,2,7,6,1).
It seems likely to me that if a target is of more than 12 digits,
most solutions for it will include numbers with more than 12 digits.
Can you prove otherwise?

However, when we are given a list of n digits and a target of
length less than n/2, I agree with you that lengths of numbers
in solutions won't exceed (n+1)/2. Moreover, it seems likely
there's some trivial solution method when target length > n/2.
So I see no need to discuss this heuristic further even if
unproved in the general case.
--
jiw
Nick
2016-12-09 11:27:26 UTC
Permalink
Raw Message
Post by James Waldby
Post by Nick
Post by James Waldby
Post by Nick
...
Post by Peter Percival
Consider the digits 123456789 in that order. Distribute addition and
subtraction signs among them so that the sum 100 results.
12 + 3 - 4 + 5 + 67 + 8 + 9
is one solution, there are others.
[big snip, separately replied to]
Post by Nick
Post by James Waldby
Post by Nick
This type of problem would normally involve
applying a few rules to identify potential solution areas
and then applying search trees. A simple type of rule
might be that a solution cannot more than 5 digits in a number.
When the target has lots of digits, a rule like that may be
difficult to prove correct.
Not really it is easy to see it must be less than half the digits.
Applying that rule when the target sum is, for example, 234567
or 456789 would result in missing out on solutions +1+234567+8-9
and -1+234567-8+9 for the one and +1+2-3+456789 -1-2+3+456789
for the other. Less trivially, suppose the digit list is as
follows: (3,4,4,9,4,2,9,5,8,4,0,3,1,7,8,4,1,2,7,4,4,2,7,6,1).
It seems likely to me that if a target is of more than 12 digits,
most solutions for it will include numbers with more than 12 digits.
Can you prove otherwise?
However, when we are given a list of n digits and a target of
length less than n/2, I agree with you that lengths of numbers
in solutions won't exceed (n+1)/2. Moreover, it seems likely
there's some trivial solution method when target length > n/2.
So I see no need to discuss this heuristic further even if
unproved in the general case.
Yes sorry, I wasn't very clear. When we are looking for the least number
it is beneficial if we can exhaustively check smaller numbers first. As
you state this heuristic can be proved not to give small solutions. I do
not know how to prove it cannot give a solution, i.e. prove a smaller
solution exists.

I was just thinking it could be proved not to give a solution length
less n/2 and

Loading...