Grass garden

grass

A garden is divided into nxn squares by footpaths. You want all the squares to be covered by grass. If at least two neighbors of a square are covered, then the grass will extend to it too. Otherwise, not. What is the minimum number of squares to be planted initially, so that the grass extends to the whole garden? Prove rigorously. No, really, make sure that your math professor would approve.

NOTE: Many have answered, but none have given a proof showing it cannot be done in fewer. Proving that you really have the minimum is the interesting part of this problem.

Did you love challenges? Then you will love LiveRamp. Apply now to join our team.

Share Button

22 Responses to “Grass garden”

  1. Chandra Jan 30, 2013 at 7:56 pm #

    The min number of square for NXN square is N .
    If we start with all square along one diagonal. So that is N squares. then all the squares will be covered.

  2. oliver Jan 31, 2013 at 8:41 am #

    The answer is n, proof by induction. Consider the 2x2 case, then grow from there.

    • Andrew Chung Mar 12, 2013 at 12:50 am #

      the proof by induction can be used to prove that n squares are needed to fill an n x n matrix, but it doesnt prove that it is the minimum, i believe.

  3. Adam Young Jan 31, 2013 at 8:47 pm #

    There are two configurartions of squares that will generate a third square. Either they are across from each other, or they are one two adjoining sides. If they are across from each other, the one in the middle will fill in. The patter will only spread as far at the furthest green patches. So if you have 2 patches, touching at the corner, it will spread up to the the top of one and down to the bottom of the other, or 4 patches. Thus the most efficient way to fill in is to take advantage of the first configuration, adjacent sides, and have it cover the most vertical and horizontal distance. It is the diagonal line down the center.

    To prove it rigorously I would start by showing it to be true for a 2X2 patch , and then showing the generating rule that for the most efficient way of adding one row and column on to a full green patch is to put a single green square in the corner. Without that square, the green will not spread. With that square, the new row and column will completely turn green.

  4. Daniel Feb 10, 2013 at 11:47 am #

    What is N?

  5. Jack Bremer Feb 11, 2013 at 4:45 am #

    3, in a diagonal.

    X--
    -X-
    --X

    Becomes

    XX-
    XXX
    -XX

    Then

    XXX
    XXX
    XXX

  6. Brian Stone Feb 15, 2013 at 1:50 pm #

    Could you please add some clarification to this problem?
    1) Does a diagonal square count as a neighbor?
    2) Are we to assume only a single "iteration" of growth?
    3) Since you noted an n*n garden, I assume you want a generic value as a function of n that answers a grid of any size n? This seems especially implicit, but discussion here and elsewhere has shown inconsistency in the solutions put forward.

    Thanks,
    Brian

    • Diane Mar 7, 2013 at 11:10 am #

      1. no
      2. you have as many iterations as it takes until growth stops
      3. yes, please give a closed-form solution in terms of n

  7. Alexander Woods Feb 16, 2013 at 8:03 pm #

    I thought about it in terms of square faces. If we only include the faces that touch other squares the vertical faces are n(n-1) and the horizontal faces are likewise n(n-1). So the initial number of faces is 2n(n-1).

    Now planting in the most efficient pattern which is clearly diagonal we lose some of the faces. Let's call the non-planted squares "passive" and the planted squares "active."

    Consider a 3x3 example. Since planting, our passive faces have decreased by a 4 + 4(n-2). Where the 4 faces come from the two active corner squares and the 4(n-2) faces are from the active middle squares. Our first decrease in passive faces is therefore:

    2n(n-1) - 4 - 4(n-2)= 2n(n-1) - 4(n-1) = 2(3)(2) - 4(2)= 4

    Now 4 faces are remaining and the garden spreads to the neighboring squares leaving 2 passive squares and presumably no faces, let's see:

    2n(n-1) - 4(n-1) - 4(n-2) = 0
    2n(n-1) - 4(n-1+ n-2)= 0
    2n(n-1) - 4(2n -1-2)= 0
    2(3)(2) - 4(2(3)-1-2) = 0

    Finally the last to squares would become garden. This pattern continues for nxn squares as shown below:

    2n(n-1) - 4(nj -1-2-3...-j)= # of passive faces for nxn garden.

    Consider again the 3x3, if we instead use n = 2 (in calculating the remaining passive faces not the original amount) the result is as follows:

    3x3 has 2(3)(3-1) = 12 initial passive faces

    12 - 4(2n -1-2) = 12 - 4(2(2)-1-2) = 8

    This doesn't necessarily mean that there are 8 passive faces left, but this number remains positive unless chosen n >= actual n. Therefore the chosen number of squares must be at least be equal to n of the nxn garden in order to complete the garden.

    I'm no mathematician, but there's a shot.

  8. cynde starck Feb 19, 2013 at 7:43 pm #

    all that is necessary is the 1st two you have showing. you can't do just one, because 2 touching is a prerequisite. the first two will make four, those four will make eight and then the ninth one will come. simple. funny that so previous posters tried to make it so complicated.

  9. Himanshu Feb 22, 2013 at 6:39 am #

    Proof :-
    The key observation here is that the parameter of the grass never increases.
    A new grass square has at least 2 neighbors, when it is added at least 2 faces of the existing squares are hidden and at most two new faces are added.
    So, every new square decreases the parameter by 0, 2 or 4. For example, consider some cases where the parameter is decreased by:
    Zero | Four | Two
    XoX X X X X
    oX o XoX XoX
    X X
    'X' represent the existing grass square and 'o' is the new grass square.

    The parameter of the final configuration is 4N. Since the parameter is non-increasing, we need at least 4N units parameter in the beginning. Every square has 4 units parameter. So, we need at least N squares.

    There are many possible configurations using N squares such that the grass extends to the whole garden. One such configuration can be obtained by placing N grass squares on the main diagonal elements. In this configuration the grass will recursively extend to the other diagonals until the entire garden is covered.

  10. Himanshu Feb 22, 2013 at 6:45 am #

    Oops, in my last comment the example cases are not properly displayed.
    These are the original examples:

    Zero:
    XoX

    X
    oX

    X
    o
    X

    Two:

    . X
    XoX

    Four:

    . X
    XoX
    . X

  11. Himanshu Feb 22, 2013 at 6:47 am #

    Oops, in my last comment the examples are not properly display.
    These are the original examples:

    Zero:

    XoX

    X
    oX

    X
    o
    X

    Two:

    . X
    XoX

    Four:

    . X
    XoX
    . X

  12. Alex Min Feb 23, 2013 at 7:09 pm #

    Given an nxn square, there are 2(n)(n-1) effective edges (discounting the perimeter of the square). When we plant n patches of grass, the grass will effectively touch 4(n) edges. In the best case scenario, each of these two edges will fill create one new patch of grass, filling in 2n more edges, and then those will fill n more edges, n/2 more edges so on...So this is kind of like a geometric series...

    where mathematically, it is a summation from i=1 to i = inf. (4n / 2^i). For the entire patch of grass to be filled up, this summation must be greater than 2(n)(n-1).

    Summarizing, this equation needs to be satisfied

    summation from i=1 to i=inf. (4N /2^i) >= 2(n)(n-1),
    where N is the number of grass patches we want to plant, and n refers to the number of grass patches in each row of the garden...

    if we choose N = n-1, meaning we plant n-1 patches of grass, the above equation will not be satisfied

    summation from i=1 to i=inf. (4(n-1)/2^i) < 2(n)(n-1).

    I'm not mathematician either...but here's a try lol

  13. Evan LaHurd Feb 26, 2013 at 12:47 pm #

    I think you can do this with induction. Just messing around with the first few cases, you get the answer of n squares needed for an n x n garden.

    If your base case is a 1 x 1 garden, you obviously just need to fill that 1 square, so our base case holds true. Now assume for a k x k garden you need k initial squares to eventually fill the garden up. We want to show that for a (k+1) x (k+1) garden, you need k+1 intial squares. This is equivalent to a garden with k^2 + 2k + 1 squares needing k+1 initial squares, using our previous k x k assumption, you can cancel out k^2 on the left and k on the right, because a garden with k^2 squares (k x k) needs k squares. That leaves us with the last 2k + 1 squares needing 1 square. If you look at all n x n possibilities (1 square, 4 squares, 9 squares, 16 squares, etc.), the number it takes to get to each successive total is 2n + 1. So for n = 1, a 1 x 1 garden that needs 1 initial square will need 1 more square for the 2(1) + 1 = 3 extra squares it takes to make a 2 x 2 garden. This means that a 2 x 2 garden needs 2 squares. For n = 2, a 2 x 2 garden that needs 2 initial squares will need 1 more square for the 2(2) + 1 = 5 extra squares it takes to make a 3 x 3 garden. This means that a 3 x 3 garden needs 3 squares. You can now see the pattern that arises from induction. I hope this is rigorous enough! :P

  14. Duong Mar 5, 2013 at 10:06 pm #

    Fact: a quare will be covered if and only if there exists at least a grass in the same row (or column).
    1. Show that N grass can covered NxN square
    2. Show that N grass can not covered more than that by contradiction.
    Obviously, if N can covered a bigger than NxN garden then there exists one row and one column with no grass.
    Pretty much it, the proof ^^

  15. Moon Bae Mar 7, 2013 at 8:19 pm #

    Based on the picture example, I made an assumption that two squares are neighbors if their faces are touching. Corner neighbors are not neighbors. If corner neighbors are allowed, this can be done with less than n.

    My approach to the problem is recursion. Just recurse until the answer becomes obviouse. In this case, it is a single sqaure(Call this x by x). Based on x by x case, find a minumum number of squares to be filled for extra squares added for (x+1) by (x+1) and add it to the minimum from x by x.

    For n = 1, at least 1 square must be filled.

    For n = 2, at least 2 squares need to be filled.
    1 square is carried over from n = 1. First, color 0 more and try to expand.
    It only covers 1 by 1, so it fails. The next minimum is 1. Color 1 more and try to expand. When two squares are filled diagonally, they expand to fill the whole garden.

    For n = 3, at least 3 squares need to be filled.
    2 squares are carried over from n = 2. I do the same as above. Try 0 more, 1 more,...so on. 1 more square, total 3 squares, in a diagonal line fills the whole garden.

    For n = 4, at least 4 squares need to be filled.
    3 squares are carried over from n = 3. 1 more square is needed to fill the whole garden, so total of 4 squares.

    So there is a pattern that, for n by n garden, at least n squares need to be filled.

    Now, Can I do better than n? (is n really the minimum for n by n garden?) No
    Let's say I can fill the whole (n by n) garden with (n-1).
    Recursively break down the garden till n = 1. (n-1) = 0 for n = 1.
    It fails. Same for (n-2), (n-3)...and so on.
    For n = 2, (n-1) = 1. Picture 1 shows that 2 by 2 cannot be filled with only one square.

  16. Michael Moldoveanu Mar 21, 2013 at 2:54 pm #

    Because the previous comments have shown that for all NxN squares the configuration of N squares filled in a diagonal is enough to fill the square.

    Lets assume a 3x3 square. Below the 0 marks that it is empty and a 1 will mark grass:

    0 0 0
    0 0 0
    0 0 0

    If N squares is the minimum number of squares needed iff N-1 fails to fill the grid. Because N works for all N, then if N-1 fails for any N, N is a better solution than N-1.

    So using the 3x3 grid, we will use only 2 squares to start growth.

    1 0 0 1 1 0
    0 1 0 becomes 1 1 0 and stops there because diagonal neighbors are not enough.
    0 0 0 0 0 0

    this will occur for any diagonal configuration of 2 squares.

    lets try a vertical orientation

    0 1 0
    0 1 0 There are no cells with 2 neighbors so it fails
    0 0 0

    Now horizontal

    0 0 0
    1 1 0 Still no cells with 2 neighbors so it fails again
    0 0 0

    Because N-1 failed for one of the N's, then N is the minimum number needed for ALL N such that a grid NxN will be filled using the rules noted above.

  17. Rachel Apr 19, 2013 at 10:22 am #

    Everyone answered n above, and I agree, but let me try to prove it is impossible with less than n by contradiction.

    Suppose for contradiction that we can cover the garden with n. This must imply that there exist some tile which can be covered with n-1 grass which is most far away from the initial patches of n-1 grass. It makes sense to pick the tile which is most far away from our initial picks because it would be hardest to fulfill the condition of having 2 neighbors (aka proximity to colored tile). The minimum number of tiles can be obtained via coloring the diagonal tiles, the intuition came from having to maximize the number of neighbors of these initial colored tile, putting them in a horizontal or vertical line would deny the spreading to 2 possible neighbors, hence not optimal. First case: I move forward to coloring the diagonal of my top left (n-1)- square in my nxn garden. In this way, I am guaranteed to have my (n-1) x (n-1) square covered. We choose to look at the square at the bottom right corner, since it will not have any neighbors getting spreaded over. But this square will not be colors, as seen in the example given in the problem.
    We now have a conjecture, in a square of size k, coloring of k-1 diagonal will leave the outermost column and row uncolored.
    Which brings us to the next possibility, where we split the diagonal coloring into 2 parts, say the first k diagonal from top left and the n-k-1 from the bottom right, perhaps the spliting might do us some good with intersection area of two squares. We might be able to get some optimal coloring this way, but we will not and this is apparent from our conjecture from first case. If we do so, it would give us two separate patches, of size k and n-k-1, which still leaves a row and a column uncolored.

    This can also be seen in terms of linear programming duality, where the solution which maximizes the condition in one case, is the minimum in its duality.

    • Sergio Apr 30, 2013 at 12:34 pm #

      Actually one don't need to cover the diagonal to get the grass spread everywhere, although one still need n initial seeds to cover a square of nxn.

      For instance, in a 3x3 square one can start by covering 3 corners and still cover the whole square

      x 0 0
      0 0 0
      x 0 x

      x 0 0
      x 0 0
      x x x

      x 0 0
      x x 0
      x x x

      x x 0
      x x x
      x x x

      x x x
      x x x
      x x x

      Another solution for a 5x5 square will be:
      0 0 x 0 0
      0 0 0 0 0
      x 0 x 0 x
      0 0 0 0 0
      0 0 x 0 0

      I thinks these solutions invalidate all the proofs presented so far, since the proofs assumed that the solution has to be in the diagonal, what is not the case.

  18. Peter Apr 28, 2013 at 7:08 pm #

    I'm surprised this is marked as unsolved; Himanshu's proof above is simple and complete. Only, where it says "parameter" it should say "perimeter", and where it says "the [perimeter] of the grass never increases" it would be clearer to say "after the initial planting stage, in the growing stage the perimeter of the grass never increases".

  19. Peter May 5, 2013 at 10:51 am #

    It’s not nearly as tidy as Himanshu’s proof above, but here’s a rough alternative proof that brings out some nice simplifying abstractions.

    Theorem T1: Any z-connected set of squares will grow to fill its spanning rectangle.
    Where z-connected means any set of squares that will eventually grow to connect, and where the spanning rectangle means the minimal rectangle that covers the set (i.e. the set’s convex hull in a 4-square space).

    Proof of T1: By definition, a z-connected set of squares will eventually grow into some contiguous shape. This shape has a perimeter made up of a sequence of turns. Turns can either be outward, i.e. away from the interior of the shape, or inward, i.e. towards the interior of the shape. Call outward turns concave and inward turns convex.
    Shapes with any concavity will grow in the next round. If after a round of growth, the new shape still has concavities, then it will continue to grow. Thus all shapes grow until they either achieve full convexity or merge with a neighboring shape. By definition a fully convex shape has only inward turns. In the square grid space, shapes with only inward turns are rectangles (including squares). This proves T1: any z-connected set of squares will eventually grow to fill its spanning rectangle.

    Theorem T2: No shape in isolation will grow beyond its spanning rectangle.
    Proof of T2: Any empty square outside the spanning rectangle can share at most one edge with the shape within the spanning rectangle.

    Restating the original problem in terms of T1 and T2: the goal is to plant an initial set of z-connected squares whose spanning rectangle is the whole garden.

    Now consider how we can build z-connected sets and how their spanning area will grow. For the following, it’s not helpful to consider the x and y dimensions of the space as distinct in any way, so just define the norm of a span to be the sum of its x and y dimensions and denote this [[A]]. Thus to cover an NxN garden we are trying to build a z-connected set A such that [[A]] = 2N.

    Also helpful to have a corollary on z-connectedness:
    Corollary C1: Assume 2 separate internally z-connected sets, A and B. A and B are z-connected to each other if and only if their spanning rectangles overlap, abut, are diagonal neighbors, or face each other across a gap of 1 empty square. This follows from T1, T2, and the 2-edge requirement for growth.

    Now assume separate internally z-connected sets A and B are placed so as to z-connect to each other (i.e. satisfy C1). There are many ways to do this, but for simplicity I’ll just cover the two cases that grow the span the most:
    * [[A + B]] = [[A]] + [[B]] if the spans of A and B are diagonal neighbors
    * [[A + B]] = [[A]] + [[B]] + 1 - 1 = [[A]] + [[B]] if the spans face each other across a gap of 1 with minimal face overlap of 1.

    For a set E consisting of a single square, [[E]] = 2. Therefore the maximal span norm of any z-connected set of N squares is 2N. Thus we need >= N squares to span an NxN garden.

    While Himanshu’s proof is much tidier, the above has some nice features (?):
    1) By following the implied algorithm for growing z-connected sets one can create every possible initial set of N plantings that will span the NxN garden.
    2) It also suggests an algorithm for testing whether an arbitrary initial planting successfully spans an arbitrary rectangular space; this method should be somewhat faster than simply iterating growth steps, and it’s much simpler for a human to reason about.

Leave a Reply