Any solution? I found an example for $\lfloor \frac{n^2}{2} \rfloor$

egxa wrote: Any solution? I found an example for $\lfloor \frac{n^2}{2} \rfloor$ Not exactly right, very close

Imaging the visual proof of the first n odd numbers summing up to n^2, with the 1x1 square beeing the one on the left bottom. Now every L shape with m squares of area Will have inside at least m-n domino ( suppose m>n ) and summing up this gives you half the bound. The other half you get from doing the same thing on the upmost right Square beeing the 1x1 of the "prof of the odd numbers" tiling ( and checking that you are'nt double counting any domino 'cause the two tilings are 'perpendicular' ). To prove that this is enought you can tile in such a way that every bound is sharp ( suppose n=5, cartesian plane coordinates, put a 3 on x=y, a 4 on x=y+1 and a 3 on x=y-1 and fill the rest with 1s and 5s, should give you n^2/2 ). The way I came up with this is by looking at the fact that #dominoes are 2n(n-1)-#(non dominoes) and if you look at the peremeter between two subsequent numbers you want that to be maximum

any solution?

Twoisaprime wrote: egxa wrote: Any solution? I found an example for $\lfloor \frac{n^2}{2} \rfloor$ Not exactly right, very close I got the same answer. Here is my solution hopefully you can point out the mistake. Answer: $$ \left\{ \begin{array}{lr} 2k^2, & n=2k \\ 2k^2+2k, & n=2k+1 \end{array} \right\} $$ Construction: The constructions for $n=7$ and $n=8$ easily generalize $$ \begin{bmatrix} 1&1&1&1&2&3&4\\ 1&2&2&2&3&4&5\\ 1&2&3&3&4&5&6\\ 1&2&3&4&5&6&7 \\ 2&3&4&5&5&6&7\\ 3&4&5&6&6&6&7\\ 4&5&6&7&7&7&7 \\ \end{bmatrix} $$ $$ \begin{bmatrix} 1&1&1&1&2&3&4&5\\ 1&2&2&2&3&4&5&6\\ 1&2&3&3&4&5&6&7\\ 1&2&3&4&5&6&7&8 \\ 2&3&4&5&5&6&7&8\\ 3&4&5&6&6&6&7&8\\ 4&5&6&7&7&7&7&8 \\ 5&6&7&8&8&8&8&8\\ \end{bmatrix} $$ Bound: Notice that any down-right path of length $n+k$ must contain $k$ dominoes. The following stuff is hard to describe but relatively straight-forward. Label the top left corner $(1,1)$ and bottom right corner $(n,n)$. Consider the down right paths that starts at $(1,k)$ pass through $(n+1-k,k)$ and ends at $(n+1-k,n)$ and the down right paths that start at $(k,1)$ pass through $(k,n+1-k)$ and end at $(n,n+1-k)$ (L-paths). These paths all contain different pairs of adjacent cells. Standard computation gives the desired bound.

sami1618 wrote: Twoisaprime wrote: egxa wrote: Any solution? I found an example for $\lfloor \frac{n^2}{2} \rfloor$ Not exactly right, very close I got the same answer. Here is my solution hopefully you can point out the mistake. Answer: $$ \left\{ \begin{array}{lr} 2k^2, & n=2k \\ 2k^2+2k, & n=2k+1 \end{array} \right\} $$ Construction: The constructions for $n=7$ and $n=8$ easily generalize $$ \begin{bmatrix} 1&1&1&1&2&3&4\\ 1&2&2&2&3&4&5\\ 1&2&3&3&4&5&6\\ 1&2&3&4&5&6&7 \\ 2&3&4&5&5&6&7\\ 3&4&5&6&6&6&7\\ 4&5&6&7&7&7&7 \\ \end{bmatrix} $$ $$ \begin{bmatrix} 1&1&1&1&2&3&4&5\\ 1&2&2&2&3&4&5&6\\ 1&2&3&3&4&5&6&7\\ 1&2&3&4&5&6&7&8 \\ 2&3&4&5&5&6&7&8\\ 3&4&5&6&6&6&7&8\\ 4&5&6&7&7&7&7&8 \\ 5&6&7&8&8&8&8&8\\ \end{bmatrix} $$ Bound: Notice that any down-right path of length $n+k$ must contain $k$ dominoes. The following stuff is hard to describe but relatively straight-forward. Label the top left corner $(1,1)$ and bottom right corner $(n,n)$. Consider the down right paths that starts at $(1,k)$ pass through $(n+1-k,k)$ and ends at $(n+1-k,n)$ and the down right paths that start at $(k,1)$ pass through $(k,n+1-k)$ and end at $(n,n+1-k)$ (L-paths). These paths all contain different pairs of adjacent cells. Standard computation gives the desired bound. The answer is correct, and your solution should also be correct. There is a simpler construction that I used during the exam.

Hi Lincoln Orz

sami1618 wrote: Twoisaprime wrote: egxa wrote: Any solution? I found an example for $\lfloor \frac{n^2}{2} \rfloor$ Not exactly right, very close I got the same answer. Here is my solution hopefully you can point out the mistake. Answer: $$ \left\{ \begin{array}{lr} 2k^2, & n=2k \\ 2k^2+2k, & n=2k+1 \end{array} \right\} $$ Construction: The constructions for $n=7$ and $n=8$ easily generalize $$ \begin{bmatrix} 1&1&1&1&2&3&4\\ 1&2&2&2&3&4&5\\ 1&2&3&3&4&5&6\\ 1&2&3&4&5&6&7 \\ 2&3&4&5&5&6&7\\ 3&4&5&6&6&6&7\\ 4&5&6&7&7&7&7 \\ \end{bmatrix} $$ $$ \begin{bmatrix} 1&1&1&1&2&3&4&5\\ 1&2&2&2&3&4&5&6\\ 1&2&3&3&4&5&6&7\\ 1&2&3&4&5&6&7&8 \\ 2&3&4&5&5&6&7&8\\ 3&4&5&6&6&6&7&8\\ 4&5&6&7&7&7&7&8 \\ 5&6&7&8&8&8&8&8\\ \end{bmatrix} $$ Bound: Notice that any down-right path of length $n+k$ must contain $k$ dominoes. The following stuff is hard to describe but relatively straight-forward. Label the top left corner $(1,1)$ and bottom right corner $(n,n)$. Consider the down right paths that starts at $(1,k)$ pass through $(n+1-k,k)$ and ends at $(n+1-k,n)$ and the down right paths that start at $(k,1)$ pass through $(k,n+1-k)$ and end at $(n,n+1-k)$ (L-paths). These paths all contain different pairs of adjacent cells. Standard computation gives the desired bound. Sorry, I wrote the answer in a more complex form, so I didn't recognize it. Besides, My construction is also different from yours.