Let $n\ge5$ be an integer. A trapezoid with base lengths of $1$ and $r$ is tiled by $n$ (not necessarily congruent) equilateral triangles. In terms of $n$, find the maximum possible value of $r$.
Linus Tang
You can pose this problem with squares instead of trapezoids: tile an $r \times r$ square with a $1 \times 1$ square removed from its corner with $n$ squares; how large can $r$ be.
Weirdly enough, this version came to the problem author in a dream where it appeared on the RELMO. Even weirder, the answer to this problem is seemingly the same as the original, but we haven't been able to find a proof—just a construction.
Let $(F_i)$ denote the Fibonacci sequence with $F_0=0$ and $F_1=1$. The answer is then $F_{\frac{n+3}{2}}$ for odd $n$ and $2F_{\frac{n}{2}}$ for $n$ even. Construction is omitted, go ask linus
For convenience, let $f(n)$ denote the maximum of the actual answers across all $0 \leq m \leq n$ ($0$ triangles corresponds to an answer of $1$) and $g(n)$ denote the claimed answer. Observe that $F_{n+2} \geq 2F_n$, so $g$ is increasing, and hence it suffices to prove that $f(n) \leq g(n)$ to prove that the original answer is at most $g(n)$.
Orient the trapezioid $\mathcal{T}$ with base of length $1$ on top. Observe that a simple angle argument implies the angles of this trapezoid are either $60^\circ$ or $120^\circ$, and since parallelograms obviously don't give the correct answer the trapezoid's shape is what we expect it to be. Also, our equilateral triangles now clearly point upwards or downwards—we will call these updogs and downdogs respectively.
I will now prove the following generalization: even if we allow "downwards-facing" (i.e. top base is longer than bottom base) $60^\circ-120^\circ$ isosceles trapezoids touching the bottom of $\mathcal{T}$ we still have $f(n)\leq g(n)$ for $n \geq 3$; refer to these downwards-facing trapezoids as downdogs as well. Observe that making a horizontal cut and removing the bottom of $\mathcal{T}$ will leave the rest tiled with either updogs or downdogs in the desired fashion.
The idea will now be to freely consider removing the bottom of $\mathcal{T}$ and inducting. Consider an arbitrary tiling with $n \geq 5$ up/down-dogs, and assume that for all $1 \leq m \leq n$ we have $f(m)\leq g(m)$. Take the bottom row of $\mathcal{T}$, which evidently must intersect at least $2$ updogs by considering the bottom corners. Pick two updogs $t_1$ and $t_2$ arbitrarily and WLOG assume that $t_1$ is at least as large as $t_2$; let their side lengths be $s_1$ and $s_2$ respectively, and let the length of the base be $L$.
Consider the top vertex of $t_2$; it is clear that it must be a vertex of some downdog, since it can't lie on two non-corner sides. The same is true for the top vertex of $t_1$. Furthermore, if $s_1 \neq s_2$ these downdogs are distinct, in which case removing the bottom of $\mathcal{T}$ with a horizontal cut through the top vertex of $t_2$ implies that the base of $\mathcal{T}$ had length at most $s_2+f(n-2)$, and using a horizontal cut through the top vertex of $t_1$ implies that the base of $\mathcal{T}$ had length at most $s_1+f(n-4)$. On the other hand, $s_1+s_2 \leq L$, so we obtain
$$2L \leq L+f(n-2)+f(n-4) \implies L \leq f(n-2)+f(n-4).$$If we had $s_1=s_2$ then performing a cut through the top vertices of $t_1$ and $t_2$ removes at least $3$ dogs and implies the base of $\mathcal{T}$ had length at most $s_1+f(n-3)$, in which case
$$L \leq \frac{1}{2}L+f(n-3) \implies L \leq 2f(n-3).$$If the first bound holds, we immediately get $L \leq g(n-2)+g(n-4)=g(n)$. If the second bound holds, we want to verify that $F_{\frac{n+3}{2}} \geq 4F_{\frac{n-3}{2}}$ for odd $n$ (essentially implying that this gives a stricter bound on $L$) and $2F_{\frac{n}{2}} \geq 2F_{\frac{n-3+3}{2}}$ for even $n$. The former is equivalent to $F_n \geq 4F_{n-3} \iff 3F_{n-3}+2F_{n-4} \geq 4F_{n-3} \iff F_{n-3} \leq 2F_{n-4}$, which is certainly true as long as $n \geq 5$, and the latter is obvious. Hence we have $L \leq g(n)$ for all tilings using $n$ dogs, and hence $f(n) \leq g(n)$ (since we already know $f(n-1) \leq g(n-1) \leq g(n)$), completing the induction.
It remains to deal with the base cases, which are $1 \leq n \leq 4$ ($f(0) \leq g(0)$ is actually false, but we don't care about this because $f(0)$ never gets "accessed" in the induction for $n \geq 5$), and show that in these instances $f(n) \leq g(n)$:
We already know $f(0)=1$.
One-dog tilings don't exist, so $f(1)=1 \leq g(1)$.
Two-dog tilings don't exist either, so $f(2)=1 \leq g(2)$.
With $3$ dogs we can get a base of $2$, but this is clearly optimal by doing a bit of casework, so $f(3)=2 \leq g(3)$.
For the case of $n=4$, the bounds on $L$ generated by the inductive step still work, and we either get $L \leq f(2)+f(0)=2$ or $L \leq 2f(1)=2$ so $f(4)=2 \leq g(4)$.
This finishes the problem. $\blacksquare$
The construction can be reverse engineered from the above sol. Here's an attached image for the odd $n$ case.
The even $n$ case follows by base case $n = 6$ with the base configuration doubled to get a length of $4$.
The sol attached above also wouldn't generalize to the square case, because if you cut up a square board you get a lot of rectangles.
This generalization might, but I think you need to flip a bunch of rows? or something.
Anyways I didn't actually do this problem, mostly out of fear. Sad.
Also if I were to word the hint, I'd probably write something stupid like $\sqrt[3]{2} < \frac{\sqrt{5} + 1}{2}$ or even stupider, $16 < 16 + 8\sqrt{5}$. god bless.
At default resolutions this attachment shouldn't be visible unless you scroll down so if you scroll down, spoiler warning! I'm not asy-ing this sorry mostly out of laziness.
IAmTheHazard wrote:
You can pose this problem with squares instead of trapezoids: tile an $r \times r$ square with a $1 \times 1$ square removed from its corner with $n$ squares; how large can $r$ be.
Weirdly enough, this version came to the problem author in a dream where it appeared on the RELMO. Even weirder, the answer to this problem is seemingly the same as the original, but we haven't been able to find a proof—just a construction.
The answer is not $\Theta(2^{n/3})$
A useful hint! After seeing it, I know I got zero points on this problem