Results 1 to 12 of 12

Math Help - grid of stairs

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    11

    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

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,100
    Thanks
    67
    Hope somebody understands what you're asking...
    I got lost at the word "stairs"
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2009
    Posts
    11
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    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 55 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:

    \begin{array}{|c|c|c|c|c|}\hline 1&3&2&3&1\\ \hline 2&5&1&5&2\\ \hline 3&4&2&4&1\\ \hline 1&1&3&3&2\\ \hline 3&2&4&1&3\\ \hline\end{array}<br />
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2009
    Posts
    11
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    807
    Thanks
    27
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Aug 2009
    Posts
    11
    Quote Originally Posted by Matt Westwood View Post
    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

    \begin{array}{|c|c|c|c|c|}\hline -&-&-&-&-\\ \hline -&1&-&1&-\\ \hline -&-&-&-&-\\ \hline -&1&-&1&-\\ \hline -&-&-&-&-\\ \hline\end{array}<br />

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    807
    Thanks
    27
    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 ...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    807
    Thanks
    27
    Actually no, that won't do at all. You can't then place 4's comfortably.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Aug 2009
    Posts
    11
    Quote Originally Posted by Matt Westwood View Post
    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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Aug 2009
    Posts
    11
    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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    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 88 chessboard, the best total that I can get is 167 (or a mean density 167/64 ≈ 2.61), as follows:

    \begin{array}{|c|c|c|c|c|c|c|c|}\hline 2&1&2&3&1&4&2&1\\ \hline 3&4&5&1&2&3&4&1\\ \hline 1&2&3&4&5&1&2&3\\ \hline 3&4&1&2&3&4&5&1\\ \hline 2&3&4&5&1&2&3&4\\ \hline 4&1&2&3&4&5&1&2\\ \hline 3&4&5&1&2&3&4&3\\ \hline 1&2&3&1&2&1&2&1\\ \hline\end{array}

    None of this is any help with the original 55 problem, since the border cells then form much too great a proportion of the total.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Ten by Ten grid
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 2nd 2009, 02:50 PM
  2. nxn grid problem.
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: October 31st 2009, 07:00 AM
  3. Stairs problem (recurrence)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 3rd 2009, 11:43 AM
  4. Help With A Grid
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 31st 2008, 12:34 PM
  5. Stairs puzzle
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: March 30th 2005, 02:25 PM

Search Tags


/mathhelpforum @mathhelpforum