Brady I want to tell you about what sounds like a totally impossible problem to solve;
and in fact by the end of this little talk it will still be impossible. On the other hand
it'll also seem quite easy paradoxically. And the title of this little story is 'Powers of
2' and you're asked to solve the following problem: you've got to pick four numbers,
integers, but they can be positive or negative - any integers you want - and you want them to
have the property that if you look at the sums of pairs of them they're powers of 2.
And you want as many powers of 2 as you can. So if you could pick four numbers
whose sum's are powers of 2, you could pick 1, 1, 1, 1 because the sum of any two of them is 2
and so there are six ways to pick two of them and we get six powers of 2 out of this. But there's
one other rule I haven't told you: the numbers have to be distinct. So we can't do 1, 1, 1, 1.
So let's do a simple case, let's start off with two numbers. So if n is 1 you can't do anything,
you can't- there are no sums of pairs if you've just got a single number. If you've got two
numbers - I'll call the value a of n as usual. If you've got two numbers you could take them to
be 1 and 3. 1 and 3 because the sum of them is 4 which is a power of 2 and there's only one sum you
can get with two numbers and so we've solved it. With two numbers you take 1 and 3. You could have
taken 3 and 5, it's not unique, but it would give you a single power of 2. Good, okay, what about
three numbers? Would you care to give me three numbers Brady that I would add? Whose sums in
pairs are powers of 2, three distinct numbers. - (Brad: Okay so a power of 2, so uh 1,
2 and 5?) Yeah not bad. Let's make it 1, 3 and 5 because that does a little better. 1,
3 and 5, how many do we get? Well 1 plus 3 is 4, good, uh 3 plus 5 is eight, good,
1 plus 5 is 6 - doesn't count, it's got to be a power of 2. That would give two powers of 2. Can
we do better? Well yes. Take minus 1, 3, and 5 - now minus 1 plus 3 is 2,
minus 1 plus 5 is 4 and 3 plus 5 is 8 - aha! We got three by using a negative number,
we've got three powers of 2. And that's the best you can do,
obviously with three numbers there are only three ways to get sums of
two numbers - three choose two is three. So that's the best possible and it worked.
What about four numbers? Call them A, B, C and D such an A plus B is a power of 2, A plus C...
There are six sums of pairs. The conjecture is you can't do it but this is an open question.
The best anyone who looks at this has been able to do is to get four numbers.
So if you take -3, -1, 3 and 5, let's look at what happens. -3 plus
5 is 2; -1 plus 3 is 2 - these can be repeated, the powers of 2 you get can have repetitions,
they don't have to be distinct. -1 plus 5 is 4 and 3 plus 5
is 8. So this set of four numbers gives you four powers of 2. As far as anyone knows that's the
best you can do. So I'm going to write down here 4? because this is still an
unsolved question. - (Because you could use really whopping big numbers couldn't you?)
It sounds impossible doesn't it? And it is. Nobody knows how to solve this. Agai- you could write
a program, say for let's call them A, B, C and D; for a for minus infinity to infinity, for B for
minus infinity to infinity, make A plus B a power of 2 and so on. - (And there are six you could do?)
We believe you can't do it, but it's an open really hard question. - (Oh we love open questions)
Yes. This was a problem of Stan Wagon's. There's a column of problems that's been run from Macalester
College in Saint Paul, Minnesota since 1968. It's- it's the problem of the week that's been going
on since then and um Stan Wagon took it over in 1993 and he's still running it. This is problem
13- problem of the week 1321. He will send out a copy of the latest problem
to anyone who's interested; this was a problem from earlier this year, pretty nice problem. - (Neil are you)
(the sort of guy who will see this and spend an afternoon trying to crack it? Or do you just go,)
(oh that's a nice problem and move on? Or do you sit down with paper and a pencil and give it some time?)
Depends on the problem. Sometimes it'll take over for a week or a month and I look up and I say, my
God I've just spent a month working on that's that problem and I'm happy to do it. This was
not one of them, no, this was obviously impossible. And actually by the time I saw the problem he'd
sent out the solution; and the the way he phrased the problem was: if you've got 10 numbers how many
powers of 2 can you get? So his question was a of 10. He said I can get 14 to solve the problem, give
me 14 powers of 2 - well if possible do better. So when he sent out the solution he said various
people found 14 and a couple of people found 15. And Rob Pratt proved that 15 is optimal;
15 is optimal for a of 10. And when I was looking at this I thought, wow, that's incredible. And I
wrote to Rob and I said, how on Earth did you do that? And he wrote back and said, no I didn't do it.
I assumed the numbers were in a certain range and with that assumption I could do the search.
Rob's a big expert on on linear programming and this is just his kind of problem. He's an expert
on MILP - mixed integer linear programming - and there are an enormous number of problems that he
can solve; but he could only solve this if he assumed that the numbers were in some range from A to B. In
fact the range that he picked in the end was, if we're looking for n numbers, let's take them in
the range minus n plus 3, n plus 3. So he assumed that each number was in that range; and
that that range he could search and optimize the number of solutions. And he came up with
um a sequence, and that sequence is now in the OEIS, but the definition- it's not Stan Wagon's definition,
unrestricted numbers, it's restricted them to this range. - (Because that's unacceptable to me, Neil.)
(Because we we recently did some videos about expressing numbers as the sum of three cubes,)
(and for some numbers to do that you had to go to incredible lengths. You had to search into the- into)
(sort of 16 or 17 digit numbers.) - Yes that's a famous a famous problem of a similar kind yes.
(So this- what Rob's done here, just restricting it like, that just seems like he hasn't solved)
(the problem at all!) - No, he doesn't claim to have solved it. And yet looking back at what he's done,
that probably is the solution or close to it. I'll tell you a bit more about that in a minute.
(Did Rob not look at four for you though to find out what-) - He certainly did. And
um and he he found this of course, he couldn't do any better. With a much bigger search - maybe not as
big as the sum of three cubes search, with numbers in the billions - but it's not clear that
would really help actually. I think probably you can't do better with four numbers. Let me continue
and look at n equals 5; if you can choose five numbers how many powers of 2 can you get? You can
get- let me write down the numbers -3, -1, 3, 5 and 11 - and if I remember correctly that's going
to give us six numbers because we will get -3 plus 5 is 2, -3 plus 11 is 8, -1 plus 3 is 2,
-1 plus 5 is 4, -1 plus- 10 - well 11 is 10, no good. 3 plus 5 is 8, 3 plus 11 is
14 - no good. 5 plus 11 is 16. And that gives us six numbers. As I said they
don't have to be distinct, this has two 2s and two 8s but that's fine, there are six powers
of 2 with five numbers. And this is the one exception that he didn't- when Rob Pratt wanted
to set limits that he could go out to 100, he the limits that he worked with were some minus
n plus 3 to plus n plus 3 and this is outside his range. For this range he found -4,
-3, -1, 3, 5 which gives five numbers - whereas this give six numbers. So we
believe that a of 5 is six, question mark. And he's gone out to 100, so that's that sequence.
Up to n equals 5 we have plausible answers. In fact we have plausible answers all the
way up really up to 100 but kind of doubtful. It's quite possible it could be
improved once we get above 10 or 12 points. 15 is probably optimal for 10 numbers; you know 10
choose 2 is 45, instead of 45 we've only gotten 15 so that's not doing very well. Maybe if you
were really clever you could do better. And Stan Wagon and Rob Pratt came up with a lower bound,
a lower bound that shows you that you can at least do moderately well in general.
...had an idea, he said um instead of having towers let's have dungeons,
let's go down. He says we're going to use the following notation, which
actually is in common use. I'll let a sub b mean read a base b-