grid of stairs

This is a problem that i thought up a couple of weeks ago but have been unable to make headway on, i was wondering if you guys could help

You are building stairs in a 5x5 grid, you wish the total height of the stair to be a maximum. you have stairs of height 1-5 to place in the grid (where the value is the height of the stair). However you cannot build a 5 height stair straight away! there are some basic restrictions, a height 1 stair can be built anywhere, a height 2 stair must be next to a height 1, a height 3, must be next to a height 1 AND 2, a height 4 must be next to a 1,2 AND 3 and a height 5 must be next to a height 1,2,3 AND 4.

So with the aim of making the biggest total for the grid, what is the optimum layout? Is it possible to generalise this to a n by m grid?

I'm new to this forum so please be nice :D

EDIT: by next to, i mean adjacent NOT diagonal
EDIT2: i think this is probably in the wrong forum, i mis-clicked :s should it be in a higher level discrete maths section?

Hope somebody understands what you're asking...
I got lost at the word "stairs" (Doh)

i think i might move this to a higher level forum - it's goes a bit beyond basic maths. When i say stair i mean steps, i may also rephrase the question to make it to do with buildings - a building of height 4 mus be next to one of height 3,2 and 1 etc.

If I understand the problem correctly, we can forget the stairs and phrase it entirely in terms of the numbers 1 to 5. We want to fill a 5×5 grid with these numbers in such a way that if a cell contains the number k then each number from 1 to k–1 must appear in an adjacent cell. We want to maximise the sum of all the numbers in the grid.

This seems like an interesting puzzle. The best total I have been able to get so far is 62, from this grid:

Yes that probably is easier to state - i tend to try and find analogies where i can, but sometimes simply stating the problem is easiest.

the other half of the problem, which i'd imagine becomes vastly more complex is to make the grid a dynamic system, where the grid must be correct at time of placement but later numbers can be replaced. e.g if you have a 3x1 grid reading 1 1 2 you could replace the centre 1 with a 2 to read 1 2 2, leaving the 2 at the end without at 1 but still allowable.

Did you use a computer program to get that grid of 62, or just guesswork?

I think I've managed to establish one thing: there needs to be at least 4 squares with a 1 in them. Otherwise there will be squares in the grid which are not adjacent to 1's.

This puzzle is excellent. Let me go and think about it some more.

Quote:

---

Originally Posted by Matt Westwood

I think I've managed to establish one thing: there needs to be at least 4 squares with a 1 in them. Otherwise there will be squares in the grid which are not adjacent to 1's.

This puzzle is excellent. Let me go and think about it some more.

---

No i'd figured that, but if you only have four 1's in the grid you cannot have any 5's. to have only 4 1's you need this layout

which does not allow for the possibility of 5's. I don't think this can be the most efficient for that reason. The way i started was to place 3 5's in the grid and see what could be worked out from there, many of these ended up impossible however.

Okay, 5 1's: one in the centre and 4 others rotationally-symmetrically placed at knight's moves away from this, on the edges. Then you can have four 5's (possibly) on the squares next to the 1's diagonal to the centre 1. That's a start ...

Actually no, that won't do at all. You can't then place 4's comfortably.

Quote:

---

Originally Posted by Matt Westwood

Okay, 5 1's: one in the centre and 4 others rotationally-symmetrically placed at knight's moves away from this, on the edges. Then you can have four 5's (possibly) on the squares next to the 1's diagonal to the centre 1. That's a start ...

---

Good start - i like the rotational symmetry thinking, but you can't get any 4's into that grid because they would be wedged between two 5's a four must border a 3,2 and 1 and it seems logical to make it border a 5. that limits it quite a lot

I have now independently made a grid totalling 62 (beating my previous 59) still haven't got any higher than that.

I wouldn't imagine this'd be too difficult to program into a computer - there are very few rules and an easy sum check, with a total of 5^10 grids it shouldn't take too long to solve surely?

Here are a few further thoughts on the problem. On an infinite grid, the best possible layout is something like this:

Code:

---

    . . . . . . . . . .
    . . . . . . . . . .
... 1 2 3 4 5 1 2 3 4 5 ...
... 4 5 1 2 3 4 5 1 2 3 ...
... 2 3 4 5 1 2 3 4 5 1 ...
... 5 1 2 3 4 5 1 2 3 4 ...
... 3 4 5 1 2 3 4 5 1 2 ...
... 1 2 3 4 5 1 2 3 4 5 ...
... 4 5 1 2 3 4 5 1 2 3 ...
... 2 3 4 5 1 2 3 4 5 1 ...
    . . . . . . . . . .
    . . . . . . . . . .

---

Here, each of the numbers 1,2,3,4,5 occurs with equal frequency, so the mean density is 3. To see that this is the best possible, notice first that every cell in the grid must either contain a 1 or be adjacent to a 1. But each 1 can only "cover" one cell together with its four neighbours. Therefore at least one-fifth of all the cells must contain a 1. Each remaining cell must either contain a 2 or be adjacent to a 2. But each 2 must have a 1 as a neighbour, and the cell itself together with its three remaining neighbours can only cover four cells. Therefore at least one-quarter of these remaining cells (or one-fifth of the total) must contain a 2. Continuing this argument, you see that in order to maximise the mean density, each number must occur with equal frequency, as in the above example.

In a large finite grid, it looks as though the above layout will again provide the optimal solution, except that some modification will be needed round the edges (for example, a 5 can never occur in a cell on the edge of the grid, and a 4 can never appear in a corner cell). As the grid gets larger, the proportion of border cells decreases, so for a sufficiently large grid it will be possible to get a mean density arbitrarily close to 3 (though never actually equal to 3).

Using that strategy on an 8×8 chessboard, the best total that I can get is 167 (or a mean density 167/64 ≈ 2.61), as follows:

None of this is any help with the original 5×5 problem, since the border cells then form much too great a proportion of the total.