Hope somebody understands what you're asking...
I got lost at the word "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
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?
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?
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.
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:
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.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 ... . . . . . . . . . . . . . . . . . . . .
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.