How did David Yang propose an ELMO problem when he's no longer in high school?

I haven't spent any time on the ELMO problems, but is this just finding a correct 5x5 tile?

borntobeweild wrote: How did David Yang propose an ELMO problem when he's no longer in high school? This problem was from last year's shortlist. Moot point though, anyone is welcome to propose problems if (but not only if) they have attended MOP previously. infiniteturtle wrote: I haven't spent any time on the ELMO problems, but is this just finding a correct 5x5 tile? No, I don't think you can achieve the bound that way.

Here's a relatively good bound for $17 \times 17$, which can be easily extended. I'm not sure this is the best though. ################# #.#.#.#.#.#.#.#.# ##.###.###.###.## #.#.#.#.#.#.#.#.# ####.#######.#### #.#.#.#.#.#.#.#.# ##.###.###.###.## #.#.#.#.#.#.#.#.# ########.######## #.#.#.#.#.#.#.#.# ##.###.###.###.## #.#.#.#.#.#.#.#.# ####.#######.#### #.#.#.#.#.#.#.#.# ##.###.###.###.## #.#.#.#.#.#.#.#.# ################.

Assume that there are $x$ white squares, consider the perimeter of the black squares $p$. It's easy to know that $p\leq 4(2^{n}+1)+4(x-1)+2$, since there must be at least one white square on the periphery of the grid. One can get that $p\geq 2((2^{n}+1)^{2}-x)+2$ from the condition. Hence, we get that $4(2^{n}+1)+4(x-1)+2\geq 2((2^{n}+1)^{2}-x)+2$ $ x\geq \frac{2^{2n}}{3}$ It's not very hard to find the construction, so we're done.

USJL can you tell something about the construction??

YaWNeeT wrote: USJL can you tell something about the construction?? By induction

I think that when I took it I wasted time finding a construction of a "conjecture" before actually solving the problem... However after I solved the problem the optimal arrangement follows easily because of the "forest" definition and the strictness of the bound.

Can someone explain(what I say appears in the official solutions) why, by double counting the edges of the squares we have 3v+1<= 4v-e <= 2n(n+1) ?

Thank you for your answers !

$3v+1\le 4v-e\iff e+1\le v$ I guess that $e$ is the number of edges where black squares are sticked. So if there's no cycle constructed by the black squares (read our assumptions), then every string of adjacent blacked squares makes a path with two or more ends (aforementioned heads of snake). Nevertheless in every path the number of edges where black squares are sticked plus one is equal to the number of squares as they don't form a cycle. But we may also have single black squares (which don't have any sticked edge), so summing the numer of edges over every disjoint black path we have $e+1\le v$ (equality comes if there are no single squares). (Path here is moving from $(x,y)$ to $(x+1,y),(x,y+1),(x-1,y),(x,y-1)$) Let me think of the second inequality...

The number of all edges on the grid is $2n(n+1)$, as there are $n+1$ rows containing $n$ edges and $n+1$ columns containing $n$ edges. The number of edges of black squares is at most $2n(n+1)$. But this is equal to $4v-e$ as every black square has $4$ edges, and $e$ edges (these shared by two adjacent black squares) were counted twice. Hence $4v-e\le 2n(n+1)$.

For the bound, consider the perimeter of the black squares. It is given that the graph of the black squares is a forest, so assume there are $m$ filled black squares and $k$ trees. We can built each tree by adding a root (+4 perimeter) and building more black cells which each contribute 2 perimeter, so total perimeter $2m+2k\geq 2m+2$. Now consider the other $(2^{2014}+1)^2-m$ squares, which are white. They each contribute at most 4 to the perimeter, and there is also the original perimeter of the square which is $2^{2016}+4$. Also note there must be one white block on the edge, that can contribute at most 2 new perimeter to the shape. So now we have a bound from above and below: $2m+2\leq 2^{2030}+2^{2017}+6+2^{2016}-4m$ so $3m\leq 2^{2n+1}+2^{n+2}+2^{n+1}+2$. The construction is as follows: Start with construction of 5x5 by not filling in OOOOX OXOXO OOXOO OXOXO OOOOO Now take the previous construction and provide one for n+1: Put 4 copies of the same construction, and make sure the X that was in the corner in the previous construction goes in the middle (they will overlap). Now add another X in the top right corner and the construction works. Proof: In each quadrant there still isn't a loop by induction. If there is a loop passing between 2 quadrants back and forth, it doesn't make sense since that would imply a loop in each quadrant. That means that they need to loop around. But we can prove by induction the only way to enter through one side and exit through another must be the loop all around, which we stopped with our final X. Proof of equality: note our construction is almost exactly according to our bounds. The only difference is that our X does not add any perimeter. But we can just check that even if we make the bound tighter we still get the same max $m$, and we are done.