Brady I want to tell you about a lovely
puzzle
that was invented by two undergraduates
at Michigan State. They call it the
stepping stones puzzle and it goes like
this: you've got a chess board, it's
infinite, and you've got a certain number
of brown stones
that are worth 1 point each.
The puzzle is you can put down the brown
stones anywhere you want - say you've got
four brown stones, that's fixed. You put
down your four brown stones and then you
add the white stones. The white stones
are numbered 2, 3, 4, 5, 6;
there's one of each value, and you can
only put down
a stone label 2
if the sum of its eight neighbours, the
sum of the eight neighbours of that
square is 2. Well you can put a 2 here
because it's got 2 neighboring squares
of value 1, and 1 plus 1 is 2, so 2 is
legal. And having put the 2 there we
could if we wanted put a 3 here, because
there's a 1 and a 2. We could have put
2 here also instead of putting it
there. We could not have put it here
because the sum of these
stones around it, namely this this and
this, are 3. So we could only put a
3 there, but we can't put a 3
there until we've placed the 2 stone,
we've got to place the stones in order.
And the puzzle is, for a given number of
brown stones that you start with, like
here's 4, how many white stones can
you put down? What's the highest number
you can get to?
So let me do it with two. - (Brady: Two browns?)
Two browns, exactly. We're gonna do it with
two browns. And we're going to work out;
if n is 1 you can't do anything, you
can only get 1, so the answer - I'll call
it a of n - if n is 2 how many- how far
can we get? Well let's try it. I'm going
to start off by putting the two brown
stones worth 1 point each, put them
there. And now there's a unique place to
get- to place the 2 which is between
them. I can put it there because 1 plus
1 is 2. Now
I can put down the 3 and I could put
the 3- I could put it there or there
or there or there. But without loss of
generality as we say I will put it there.
So now we have to find a place to put
the 4.
Well, I could put it here because the 1
and 3 makes 4. But it's a little
better to put the 4 here because then
this frees up
this square for the 5. We've got to
put the 5 somewhere, we've got to make a
place for the 5, so I'm going to put the
5 there. And it's legal because it's got
two neighbours: 1 and 4. Now what about the
6? Well there's a choice. We could put the
6 here- no no I can't put it there
because that's got neighbours 5, 4
and 1 - I could only put a 10 there.
You've got to put them in order, yes,
you've got to build your way up. - (So it's)
(not what's the highest value can I get)
(on the board? It's what's the highest)
(value I can get on the board building in)
(order?) - Building in order, yes.
It's like climbing a mountain, you've got
to get- work your way up. - (Oh I can see)
(where you can put a 6)
Here right? - (Yeah)
Yeah,
all right,
6. It's legal because we've got a 1, a
2 and a 3 - makes a 6. We could
have put it there too but I like
putting it here. - (Does that not now)
(invalidate the 3? The 3)
(remains valid?) - The 3 main- remains
valid because when it was built its
neighbours added up to 3 and and
that's fine and then we can use it
to build up other things. Yes. All right,
7, where are we going to put 7?
I'd like to put the 7 here
because it's got neighbours 1 and 6
so that works. Now what about the 8?
How about here because then we've got
the 1, 4 and the 3 adding up to
8. Now what about the 9? Well here
would be a good place for the 9,
but that looks promising
because I can see where to put the 10.
The 10 can go here because we've got a
4 and a 5 and a 1. Okay, now I
think it'll be easy now because we
continue that thread. We'll put an 11
there, now the 12 -
there's going to be a clever place to
put the 12.
Here. The 12 is a bit of a nuisance
because we really want to get down to
using the 13 and the 14. We have to,
so to speak, place the 12 in a way that
won't interrupt us. Because you can see
that we have a 13
square here, the 6 and the 7, and
now now we've got a 1, a 6 and a 7
so we can put the 14 there. And we can
put the 15 there with the 1 and the 14,
and we can put the 16 here. Now I
carefully provided stones labelled
through 16 because I knew that 16 was
the best we could hope to do.
The two undergraduates who came up with
this puzzle worked this out. They proved
that you can't do better than 16 with
two starting stones. - (Because- because you)
(could put the starting stones in)
(different positions, but that's the)
(optimal position to put them in is it?)
(Where you- where you placed?) - Yes yes. What
makes this an interesting challenge is
that in fact you could put the starting
stones anywhere you want in the whole
world.
So if you were writing a program to
search for this you could say, for you
know x1 from minus infinity to infinity
from- but of course you don't do that. You
say without loss of generality we can
put the first stone there and then
there's really only one good place for
the second stone, but then the number of
possibilities increases. Initially it's
an impossible sounding problem but in
the end we
can do pretty well. So that's the
solution with with two starting stones,
all right, so and it's 16. And
we know a few more terms: so we actually
know
only six terms and the sixth is 60 and
three is 28,
four
is 38,
and five
is 49.
That's all we know.
We don't know seven, no one has been able
to work it out.
And maybe it's because nobody has really
tried hard. - (Do we know the stone)
(configuration for 3, 4, 5 and)
(6? We obviously do.) - We know one, yes. It's
not necessarily unique. Here for example
are the configurations for four stones,
we you put the starting stones, the brown
stones, in these places and then you work
it out and eventually you can get up to
38 there. And with six starting stones,
that's the starting pattern, and you can
get to 60. Now one thing I was expecting
you to ask me Brady is, how do you know
it's finite? Maybe if you're really
clever you can put down the 2 and the
3 and the 4 and 5 and go
around in this in a spiral
and get
very large numbers. Well that's not
possible
and I will prove it. I can also give you
a lower bound, I can show you that you
can do at least
this well.
This is a construction of Andrew Howroyd.
Look at this, look at this construction.
We're gonna put down a 1, a brown stone
here, leave a gap there, and put a 1
here. These are the two brown stones. And
then we can put a 2 here; then we can
put a 3,
a 4, a 5, and a 6 there. And then
he said let me have pre-placed a 1
here.
If we do that then we can put a 7
here, and then we can put an 8 and a
9 and a 10 and an 11 there,
very cunning.
And then we're going to put a 12 there
in a minute; so let us have pre-placed
another brown stone there and then we
can get 12, 13, 14, 15, 16. And there in a
minute we'll go 17.
So each-
each brown stone
buys us five more steps.
When we put down that brown stone we
were able to add 12, 13, 14, 15 and 16.
And here we got five and here
we got five. So with n
starting stones, n brown stones, this is
not the best you can do but it certainly
shows
that you can get at least five n minus
4, because each time you add one more
brown stone. So here with two brown stones
we went up to 6, and if I put n equals
2; two brown stones, 5 times 2
minus 4 is 6. Three brown stones we
went up to 11. - (And this thing's going)
(in a straight line?) - It's going in-
(It's not gonna twist it back on itself?)
No, it's a zigzag.
So
we just do in a zigzag like that and
keep going.
It's a very simple-minded construction
and I wouldn't be at all surprised if
some ingenious person viewing this can
come up with something that does wrap
around itself and give a much better
lower bound. But at least we know it
grows linearly, 5n minus 4.
Now what about in the other- the other
direction? Can we put a limit on how many
you can get?
And
for that I need another piece of paper.
Is there any limit to how many you can
get? If you've got three brown stones
what's the maximum possible you could
ever hope to get?
You might think you could get infinitely
many. And the way I think of this is it's
a kind of a mountain climbing problem.
You want to get as high as you can, but
in order to get to that height you have
to build steps up the mountain to get
there. To get to height 31,000
up at Everest you've got to have steps
in the mountain that are labelled with
all the numbers down to 1, and the 1
being what any one of the huts. I think
of the brown stones as huts, brown being
a good colour because the huts are
usually down on the ground. And the white
of course corresponds to the ice where
you're cutting the steps, the snow fields
that you're ascending.
So let's suppose
you could get to a very high point; and
this argument from Robert Gerbicz says
let's look at a really high point, let's
call it H.
It's a square where we got very high up.
How did we get there? Well it's got eight
neighbours. How could you get 100? To
get 100 you must have had some
pretty big numbers around it. You could
have had for instance an 80 and a 20. We
could have had a 50, a 49, and a 1 - the 1
would be a hut, a brown stone. I want to
argue
that there must be
a fairly small stone somewhere in the
neighbourhood; if there's a 1 so much
the better, but there there has to be a
stone
around it
which is less than or equal to 50.
In fact less than or equal to 49, but
never mind. If if we've got H here one
of these stones - I don't know which one -
is less than or equal to H over 2.
Because if all the stones around it were
bigger than H over 2 we wouldn't- we'd
get a number bigger than H here. So one
of the eight,
at least one of the eight, has to be at
most H over 2,
a neighbour of this.
Well look at the neighbours of that.
The neighbour of this H over 2,
one of them must be at least,
at most, H over 4 -
say there.
And the neighbour of that must be at most
H over 8.
And so after going-
after going d steps
from this high point there must be a
square with at most H over 2 to the d.
But if we go far enough
that's got to be a 1. - (What's got to be a 1?)
The small one
you get to. The high point has to have a
neighbour at most
H over 2, a neighbour of that has to be
at most H over 4, the neighbour of
that most H over 8. Each time we go
one step further away we can divide by a
power of- another power of 2. So for
instance to have a concrete example I
was going to use Everest. It's a little
easier if I take 65,000. Suppose
we could get up to 65,000. 65,000 is
just less
than 2 to the 16, which is 65536.
So I've picked a number here
just a bit under 2 to the 16. And
so following this path, you're always
taking the smallest neighbour, we will
eventually get down to a 1 in at most
15 steps. So from here to here- so if it's
655- think that means within a
radius of 15 there's a 1, there's a hut
at one of our starting things.
All right so now
let's suppose that we could get to
65,000 using just three 1s.
Let me prove that's impossible.
So let's say we have our
high point here,
65-
65,000 - twice as high as
Everest. And
within a square of side 15, within a
square around it
of size 31x31 there has to be a hut
somewhere.
So a brown
starting stone. Let's suppose we were
able to get to 65,000 with just three
starting stones. Here's a starting stone,
here's a starting stone,
and here's a starting stone. And we know
that somewhere within distance 15 of one
of these three is the 65,000. So if I
draw the squares
around it of size 31, and around here
size 31, and around this one of size 31;
inside one of these three squares of
size 31 is our high point, is our point
higher than mount Everest, the
65,000 is within one of these three squares.
That's what I just proved. But
that's going to be impossible because
not only do we have to get
65,000 we have to get
all the numbers up to it. We have to get
all the numbers in these squares:
1, 2 -
well we've got the 1 - we have to get
2, 3, 4,
all the way up to
64,999 before we can get to
the top. It's not going to work because
inside this square
there are only 31 square stones, less-
961, less than 1,000. So we've got
1,000 square here, 1,000 squares
here, 1,000 squares here. Total of at
most 3,000 squares. On the other
hand we have to get 65,000
stones to get up there. So it's a
contradiction, so you can't do it with
three stones. Three stones are not enough
to get to 65,000. - (You can't create)
(branches that come out of the squares?) - No
because if there was a stone at 10,000
there still has to be
a 1 within
10,000 divided by what-
the appropriate power of 2. They all
have to be within the squares of side 31
centred at the three huts. Everything
we do has to be within these
these three squares.
(So what does that mean for our upper bound?)
So our upper bound, yes. So what
this actually gives if you do it
properly is about n log n for the upper
bound. But
Robert Gerbicz
fine-tuned the argument and taking
care of what happens around the huts,
the small numbers, doing that counting
more delicately. And he proved in fact
you can't get more than 714 n.
If you have n huts, n brown stones,
the highest you can get is 714 times n.
So we know you can't get arbitrarily
high.
(But that initial sequence you showed me-)
Went up to six- went up for six terms, yes.
(And that wasn't 714 times n.) - No it's just
an upper bound. He's- he he's just proving
that you you cannot hope to do any
better no matter how clever you are. In
fact you can't do anywhere near as well
but it's just-
it's just a theoretical upper bound.
The answer is 0. What about a 3x3?
If we put a black queen here it
attacks all the squares except these two.
So we could put a white queen here. We
could put a white queen here too but
we'd have two white queens and we can
not put two black queens. So the numbers
have to be equal, okay. All you can do is
one. One of each colour.