Am I missing something? We are to find the number of 4-tuples $(k_1, k_2, k_3, k_4)$ satisfying $k_1+k_3=k_2+k_4$, $0\leq k_i\leq n$?

Proposed new wording for question 4 - it's a limerick! I once had an n-height square table That I wanted to stand on a gable. So I hired a plumber Who cut a whole number From each leg, so the table stayed stable. With the given information, and assuming each leg is distinct before cutting, how many ways could the plumber have cut the legs of my table?

Quote: With the given information, and assuming each leg is distinct, how many ways could the plumber have cut the legs of my table in terms of n? But each leg doesn't have to be distinct after each cut. By the way, myth is right -- K1 + K3 = K2 + K4. Another way to look at it is if l1, l2, l3, and l4 are the legs after the cuts l1 + l3 = l2 + l4 Then its all about finding a formula...I'll post it once the USAMO formula opens up again. JB

Myth wrote: Am I missing something? We are to find the number of 4-tuples $(k_1, k_2, k_3, k_4)$ satisfying $k_1+k_3=k_2+k_4$, $0\leq k_i\leq n$? That's absolutely correct, but how did you come up with that so fast? It took me a few minutes to get around that fact. Then it took me quite a few more to convince myself (with the help of the table I was working on, which imagined its legs being cut off) it's true.

Hmm... What is the problem? I just wrote the condition that four points lies in the same plane, i.e. they are complanar. Indeed, it immediately kills the problem, since we can easily count all such quadruples.

jackb1115 wrote: Quote: With the given information, and assuming each leg is distinct, how many ways could the plumber have cut the legs of my table in terms of n? But each leg doesn't have to be distinct after each cut. I meant that the legs were distinct before the cut.

Could you explain why it's obvious that "coplanar 4-tuple" obviously implies Myth wrote: $(k_1, k_2, k_3, k_4)$ satisfying $k_1+k_3=k_2+k_4$, $0\leq k_i\leq n$ ? I eventually used an argument stemming from the fact that if there were to be a leg coming from the center of the table, it would have to be the average of k_1 + k_3 and k_2 + k_4, which led (with a bit of work) to the same conjecture you cited.

Hmm... I think your arguments have the same core with my arguments. Actually, I simply used the fact that, clearly, a plane intersects regular square prism on parallelogram (sorry for my english). BTW, why did you change your flag?

I took this approach: First, we count the number of ways of cutting the same length off each leg, which is clearly (n+1). We note that making three integral cuts determines the length of the fourth cut, and furthermore that the fourth cut must have integral length. Also, the shortest cut must be across from the longest cut. For the cases where we do not cut the same length from each leg, we assume WOLOG that k1 is the shortest cut, making k3 the longest cut, and if there are two shortest cuts, let k2 be the other one. Later we will multiply our count here by 4 so that we count when each of k2, k3, and k4 are the shortest cuts (and we don't count any cases more than once). Then 0 <= k1 <= k2 < k3 <= n; we want the number of solutions to this, which is equivalent to 1 <= a1<a2<a3 <= n+2, when a1=k1+1, a2=k2+2, a3=k3+2. This is just (n+2 choose 3). So our total is n+1 + 4(n+2 choose 3)

here's how i did number 4, it's essentially the same as everyone else's method: let Lx be the length of leg x, and Px be the endpoint of leg x. say that L1 is directly across from L3(diagonally). in order for the table to be stable, the line that passes through P1 and P2 must be paralell to the line that passes through P3 and P4. the condition L2 - L1 = L3 - L4 ensures that the 4 points are coplanar let the difference L2 - L1 = m since the problem states that each leg can either be cut entirely, not cut, or cut integrally, m must be an integer on the domain [0,n] if there are two adjacents legs with length n, then there are (1+n-m) different cuts that will produce this difference. the pair of legs opposite these two must have the same difference, but can still be cut in any of the (1+n-m) ways. thus we take the following sum: sum of (1+n-m)^2 from m=0 to m=n since we have restricted m to be greater than or equal to zero, we have neglected to count the cases in which L1 is greater than L2. thus we multiply the sum by two, for there are just as many cases in which L2>L1 as those in which L1>L2. but what about when m=0? at m=0 the expression only needs to be counted once, thus to avoid overcounting, we subtract the number of cases in which m=0 (there are (1+n)^2 such cases. if we examine the sum of (1+n-m)^2 from m=0 to m=n, we note that the first term will be (1+n)^2 and the last term 1^2. so this is essentially the same as the sum of the first (1+n) squares. plugging into the formula x(x+1)(2x+1)/6 and performing the said process to count accurately, we have: 2*(n+1)(n+2)(2n+3)/6 - (1+n)^2 = (n+1)(n+2)(2n+3)/3 - (1+n)2 =[(n^2+3n+2)(2n+3)-3(n^2+2n+1)]/3 =(2n^3+3n^2+6n^2+9n+4n+6-3n^2-6n-3)/3 =(2n^3 + 6n^2 +7n + 3)/3

I interpreted "Note that a cut leg of length 0 is permitted" to mean "Cutting off a leg by a length of 0 is permitted" but that a length of 0 after cutting would leave no table leg, and would be non-permissible. I also put in my solution that if it was meant to be interpreted "A leg of length 0 after cutting is permitted" then all the "n" in my solution could be replaced by "n+1". Would they take off a mark for that? (My solution above is with the accepted interpretation - but on the contest, I put n+4(n+1 choose 3) instead of n+1+4(n+2 choose 3)

I did this differently from the way CodeBlue did: I took the sum of the number of 4-tuples meeting the condition and having maximal element $i$, for $i = 0$ to $n$. To find these, I took the sum of the number of tuples $(k_1,k_2,k_3,k_4)$ for $m = n$ to $2n$, such that $k_1 + k_3 = m$. Since the maximum element had to be i, I set $k_2 = n$. Then $k_4$ is fixed, and we get that the number of these tuples is $2n - m$. There is one overlap here when you rotate (when $k_1 = m - n$ and $k_1 = n)$, so get rid of one of them, and you get $2n - m - 1$ tuples. Multiply this by four, then sum them and add one for $m = 2n$. You get, for $j$ between $n$ and $2n-1$, $4 \sum (2n - j - 1) + 1$, which is equivalent to, for $j$ between $1$ and $n$, $4 \sum j + 1$. Then replace n with i, and we take the sum of this for $i$ between $0$ and $n$. Eventually, I get the same answer as CodeBlue87 did (some reassurance that I did it right).

MithsApprentice wrote: Could you explain why it's obvious that "coplanar 4-tuple" obviously implies Myth wrote: $(k_1, k_2, k_3, k_4)$ satisfying $k_1+k_3=k_2+k_4$, $0\leq k_i\leq n$ ? I eventually used an argument stemming from the fact that if there were to be a leg coming from the center of the table, it would have to be the average of k_1 + k_3 and k_2 + k_4, which led (with a bit of work) to the same conjecture you cited. Should be immediately obvious

I did $k_1+k_4=k_2+k_3$, did cookies and kids, and got the answer to be \[ 2\sum\limits{k=1}^{n}{k^2}+(n+1)^2=\frac{2n^3+5n^2+5n+2}{3} \] I allowed a leg of length 0.

How about this solution: Let $ C_i$ be the number of sets of cuts $ \{k_1,k_2,k_3,k_4\}$ that result in the longest leg being of length $ i$. Then $ C_i=C_{i-1}+x$, and we will evaluate $ x$ to develop a recursion. Note that if a set of cuts has non-zero cuts, then if that set is counted in $ C_i$, subtract $ 1$ from each of the cuts to obtain a set of cuts that is counted in $ C_{i-1}$. For example, if $ \{2,3,4,5\}$ was counted in $ C_5$, then $ \{1,2,3,4\}$ would have been counted in $ C_4$ because subtracting the same length from each leg preserves the quality of the legs being coplanar, and there is a bijection. Now we must evaluate those sets of cuts that don't fall in this bijection, which are clearly those where one leg is completely cut off. After some simple geometric reasoning that I won't include here, we see that one corner has a leg of length of zero, and the opposite leg, called the initial leg, will have length $ i$ If the remaining legs have length $ y$ and $ z$, $ (y,z)=(0,i),(1,i-1),...,(i-1,1),(i,0)$, so $ i+1$ options. The initial corner can be any of the four legs, but each of the four permutations of the set of cuts $ {0,0,i,i}$ is repeated twice, so we have $ 4(i+1)-4=4i$ total additional sets of cuts. We conclude that $ C_i=C_{i-1}+4i$, and note that $ C_0=1$. Now we can create generating functions. $ F(x)=\sum_{i=0}^\infty C_is^i$. Also, $ G(x)=\sum_{i=1}^\infty 4i$. From the recursion, we have \[ F(x)=C_0+xF(x)+G(x)\Longrightarrow F(x)=\frac{1+G(x)}{1-x}\] This final equation is easy to analyze. Simply use $ G(x)$ as the first term of a geometric series with constant multiplier of $ x$. This gives $ C_i=2i^2+2i+1$. The total number of sets of cuts for a table of legs of length $ n$ is the sum of all the $ C_i$, $ 0\le i\le n$, from which we deduce the answer $ \frac{2n^3 + 6n^2 +7n + 3}{3}$.

Why so much overkill?! Here's the first complete non-overkill solution in the thread. As noted, it's immediately obvious that the condition is equivalent to $ k_1+k_3=k_2+k_4$. To count these, fix the sum to be $ s$; clearly $ 0\le s \le 2n$. For $ s\le n$, we have that there are $ s+1$ (ordered) ways to partition $ s$ into two parts; consider $ (s-i,i)$ with $ i$ ranging from $ 0$ to $ s$. $ s>n$ is in one-to-one correspondence with $ s<n$; replace $ s$ partitioned into $ x+y$ with $ 2n-s$ and $ (n-x)+(n-y)$. Because we're choosing the partitions of $ s$ with replacement, our final sum is $ 1^2+2^2+3^2+\ldots+n^2+(n+1)^2+n^2+\ldots+3^2+2^2+1^2$. Using the formula for the sum of $ n$ squares, this comes out to $ \frac{2n^3 + 6n^2 +7n + 3}{3}$ and hence this is our answer, as desired.

What a weird problem. Hardest part is probably noticing what the condition means. We claim that the condition is equivalent to the claim that $a+d=b+c=k$ for some $0\leq k\leq 2n,$ where $a\leq b\leq c\leq d$ are the leg lengths. This is because $\vec{A}+\vec{D}=\vec{B}+\vec{C}$ where $A,B,C,D$ are the vertices of the square in that order. Looking at the component parallel to the legs finishes. Obviously for $0\leq k\leq n$ there are $(k+1)^2$ tables, which corresponds to $\frac{(n+1)(n+2)(2n+3)}{6}.$ Now for $n+1\leq k\leq 2n,$ send $a\to n-a'$ and $d\to n-d'.$ Then $a'+d'=2n-k,$ so there are $(2n-k+1)^2$ tables, which corresponds to $\frac{n(n+1)(2n+1)}{6}.$ Add it all up to get \[\frac{2n^3+6n^2+7n+3}{6}.\]

Assume the $L_i$ are numbered clockwise. The table is stable if and only if the new ends of the tables are coplanar. Given three choices of table leg lengths removed, $k_1,k_2,k_3$, the fourth must be uniquely determined by intersecting the plane with the fourth leg. But also, the midpoint the segment between the table leg endpoints of $L_1$ and $L_3$ and the midpoint of the segment between the table leg endpoints of $L_2$ and $L_4$ must coincide because the table is square. That is, $((n-k_1)+(n-k_3))/2 = ((n-k_2)+(n-k_4))/2$, or $k_1+k_3=k_2+k_4$. For a particular integer $0\le a\le n$, there are $(a+1)^2$ choices of $(k_1,k_2,k_3,k_4)$ with $k_1+k_3=k_2+k_4=a$ and for $n+1\le a\le 2n$ there are $(2n+1-a)^2$ choices. So overall there are \[(n+1)^2 + 2\sum_{i=1}^n i^2 = (n+1)^2 + 2\cdot \frac{n(n+1)(2n+1)}{6} = \frac{n(n+1)(2n+1)+3(n+1)^2}{3} = \]\[\frac{n+1}{3}\cdot (n(2n+1)+3(n+1)) = \frac{n+1}{3}\cdot(2n^2+4n+3) = \frac{(n+1)(2n^2+4n+3)}{3}.\]

This problem is a bit ambiguous. 1. The problem doesn't state the legs are all parallel. 2. The problem doesn't specify whether a cut of length $n$ is allowed. I interpreted it as a cut of length $n$ not being allowed, ending up with a different answer. My solution is similar to post 18. 2021 Fall AMC 10A #17 has basically the same idea.

Define $a_i = L_i - k_i$ for all integers $i \in [1, 4]$. Linearity of Height implies that it is necessary and sufficient to have $a_1 + a_3 = a_2 + a_4$, where $L_1$ and $L_3$ are diagonally opposite wrt the square. Now, it's clear that the number of satisfactory $4$-tuples is just $$\sum_{i = 1}^{n + 1} i^2 + \sum_{j = 1}^{n} j^2 = \frac{(n+1)(n+2)(2n + 3)}{6} + \frac{n(n+1)(2n+1)}{6} = \frac{2n^3 + 6n^2 + 7n + 3}{3}$$which finishes. $\blacksquare$ Remark: This solution is probably too terse for the actual USAMO; I'm just lazy.

Lemma: $k_1+k_3=k_2+k_4$. Proof: Define $L_1=(1,1,z_1), L_2=(1,-1,z_2), L_3(-1,-1,z_3), L_4=(-1,1,z_4)$. If $\alpha$ is a plane with the equation $ax+by+cz=d$, then: $a(1)+b(1)+c(k_1)=d\implies k_1=\frac{d-a-b}{c}$ $a(1)+b(-1)+c(k_2)=d\implies k_2=\frac{d-a+b}{c}$ $a(-1)+b(-1)+c(k_3)=d\implies k_3=\frac{d+a+b}{c}$ $a(-1)+b(1)+c(k_4)=d\implies k_4=\frac{d+a-b}{c}$ $\implies k_1+k_3=k_2+k_4$. From this we can easily conclude that the number of ordered 4-tuples is $2\sum_{k=1}^{n}k^2+(n+1)^2=\frac{2n^3+6n^2+7n+3}{3}$. $\blacksquare$

Notice we must have $k_1+k_3=k_2+k_4$ where $0\le k_i\le n.$ The number of solutions to this equation is $$\sum_{i=0}^{n}{(i+1)^2}+\sum_{j=1}^{n}{j^2}=\frac{2n^3+6n^2+7n+3}{3}.$$by casework on whether $0\le k_1+k_3\le n$ or $n+1\le k_1+k_3\le 2n.$ $\square$

Restate the problem in terms of $k_i$: Rephrased Problem wrote: Find the number of ordered tuples $(k_1,k_2,k_3,k_4)$ of integers such that $k_1+k_3=k_2+k_4$ and $0\le k_i\le n$ ($i=1,2,3,4$). Let this common value be $t$, with $t$ fixed. If $0\le t\le n$, there are $t+1$ ways to choose $k_1$ and $t+1$ ways to choose $k_3$, then the tuple $(k_1,k_2,k_3,k_4)$ is uniquely determined. If $n<t\le2n$, then we have $t-n$ choices for $k_1$ and $t-n$ choices for $k_3$. Then the answer is: $$\sum_{t=0}^n(t+1)^2+\sum_{t=n+1}^{2n}(t-n)=\frac{(n+1)(n+2)(2n+3)}6+\frac{n(n+1)(2n+1)}6=\frac{2n^3+6n^2+7n+3}3.$$

Set the table in the $xy$ plane such that WLOG it’s coordinates are $(1,1),(-1,1),(-1,-1),(1,-1)$, corresponding to $L_1,L_2,L_3,L_4$, respectively. The problem statement is equivalent to there being a plane passing through the four ends of the legs, and since a plane is determined by three points, we will fix $L_2,L_3,L_4$. The coordinates of these points are $(-1,1,n-k_2),(-1,-1,n-k_3),(1,-1,n-k_4)$. The plane passing through these points is $(k_4-k_3)x+(k_2-k_3)y+2z=2n-k_2-k_4$. Then at $x=y=1$, we have $z=n-k_2+k_3-k_4$. Going back to our problem statement, it is necessary and sufficient to have $n-k_1=n-k_2+k_3-k_4\implies k_1=k_2-k_3+k_4$. We use generating functions. Our problem becomes finding the sum of the coefficients of the terms in the expansion of $(1+x+x^2+…+x^n)^2(1+x^{-1}+x^{-2}+…+x^{-n})$ that have an exponent between $0$ and $n$, inclusive. This expands to $(1+2x+3x^2+…+(n+1)x^n+nx^{n+1}+…+x^{2n})(1+x^{-1}+…+x^{-n})$, and from here our desired value is $\sum_{k=0}^{n+1} k^2 +\sum_{k=0}^{n} k^2=\frac{n(n+1)(2n+1)}{6}+\frac{(n+1)(n+2)(2n+3)}{6}=\boxed{\frac{2n^3+6n^2+7n+3}{3}}$

Notice that $k_1+k_3=k_2+k_4$ because all four of the leg ends must lie on the same plane. Notice that when $k_1+k_3=k_2+k_4=x\le n$, there are $(x+1)^2$ ways to pick $k_i\le n$. This gives us $\frac{2n^3+9n^2+13n+6}{6}$ ways. Notice that when $k_1+k_3=k_2+k_4=x>n$, there are $(2n-x+1)^2$ ways to pick $k_1\le n$. This gives us $\frac{2n^3+3n^2+n}6$ ways. In total, there are $\frac{2n^3+6n^2+7n+3}3$ ways.

The main claim is the following: Claim. The table is stable if and only if $k_1+k_3=k_2+k_4$. Proof. Observe that for the four vertices of the legs to be coplanar, they must form a parallelogram because the quadrilateral formed is the projection of a square. Thus, equating coordinates yields the result. $\blacksquare$ Now, we can simply split into cases based on the value of $k_1+k_3$ to get the answer $$2\sum_{i=1}^n i^2 + (n+1)^2 = \frac{(n+1)(2n^2+4n+3)}3.$$

We must have $k_1 + k_3 = k_2 + k_4$. So, since $0\leq k_1, k_2, k_3, k_4\leq n$ we do casework on the possible values of $k_1+k_3$ and arrive at our answer of \[2(1^2 + 2^2 +\cdots +n^2)+(n+1)^2 = \frac{2n^3+6n^2+7n+3}{2}.\]

I claim that there are exactly $\frac{2n^3+6n^2+7n+3}{3}$ ways to cut the legs of the table. We use 3D-coordinate geometry. WLOG, let the side of the square table be $s$. In order to have a "stable" table, we must have $(0,0,k_1)$, $(s,0,k_2)$, $(s,s,k_3)$, and $(0,s,k_4)$ be on the same plane. (We consider $(0,0,0)$ to be the end of leg $L_1$ before the cuts.) Taking the three legs $L_1$, $L_2$, $L_3$, we find that the equation of the plane containing the three ends of those legs is \[\frac{k_1-k_2}{k_1}x+\frac{k_2-k_3}{k_1}y+\frac{s}{k_1}z=s,\]and plugging in $(0,s,k_4)$, we have that $k_4=k_3+k_1-k_2$, meaning that the question is equivalent to (USAMO 2005/4, Rephrased) Find all ordered quadruples of nonnegative integers $(k_1,k_2,k_3,k_4)$ such that $k_i\leq n$ and $k_1+k_3=k_2+k_4$. Let the sum be $x$. Note that if $x\leq{}n$, then there are $x+1$ ways to partition $x$ into two nonnegative integers less than $n$. If $x>n$, we have that there are $2n-x+1$ ways to partition $x$ into two nonnegative integers less than $n$. Using this, we find that there are \[1^2+2^2+\dots+n^2+(n+1)^2+n^2+\dots+2^2+1^2=\frac{2n^3+6n^2+7n+3}{3}\]possible ordered quadruples, finishing the problem.

Myth wrote: Am I missing something? We are to find the number of 4-tuples $(k_1, k_2, k_3, k_4)$ satisfying $k_1+k_3=k_2+k_4$, $0\leq k_i\leq n$? When $x \le n$, $k_1+k_3=x$ has $x+1$ solutions, and $k_2+k_4=x$ also has $x+1$ solutions, so total is $(x+1)^2$ per $x$ Total for this case: $1^2+2^2+...+(n+1)^2=\frac{(n+1)(n+2)(2n+3)}{6}$ Otherwise, $k_1+k_3=x$ has $2n+1-x$ solutions, and $k_2+k_4=x$ also has $2n+1-x$ solutions, so total is $(2n+1-x)^2$ per $x$ Total for this case: $n^2+(n-1)^2+...+1^2=\frac{n(n+1)(2n+1)}{6}$ The totals sum to $\frac{2n^3+6n^2+7n+3}{3}$

0 MOHS so hard Note that the points $(0, 0, n-k_1)$, $(0, 1 n-k_2)$, $(1, 1, n-k_3)$, and $(1, 0, n-k_4)$ are coplanar. Realize that the points are coplanar if and only if $k_1+k_3 = k_2+k_4$. Thus we want the number of solutions $(k_1, k_2, k_3, k_4) \in \{0, 1, \dots, n\}^4$ such that $k_1+k_3=k_2+k_4$. Employ gen func. Then we want the sum of the squares of the coefficients of \[ (1+x+\dots+x^n)^2, \]which has coefficients $1$, $2$, ..., $n+1$, $n$, $n-1$, ..., $1$. The sum of their squares is \[ \frac{n(n+1)(2n+1)+(n+1)(n+2)(2n+3)}{6} = \frac{2n^3+6n^2+7n+3}{3}, \]which is the answer.

The feet of the legs are coplanar iff $k_1+k_3=k_2+k_4$. Thus casework on this equal value gives our answer of \[1^2+2^2+\ldots+n^2+(n+1)^2+n^2+\ldots+2^2+1^2 = \boxed{\frac{2n^3+6n^2+7n+3}{3}}. \quad \blacksquare\]

Let the point where $L_i$ meets the table top be $V_i$, and the point where it touches the ground after being cut be $F_i$. Clearly, the slope of $V_1V_2$ must be equal to that of $V_4V_3$, giving us $n-k_1-n+k_2 = n-k_4-n+k_3 \implies k_2-k_1 = k_3-k_4$, and the number of 4-tuples satisfying this is clearly $2 \cdot \sum_{k = 1}^{n} (n+1-k)^2 + (n+1)^2$, which is easy to simplify.

Consider the table before the cut. Orient the plane with $(0,0,0)$ being the bottom of $L_1$. Let the floor be the plane \[ax+by+cz+1 = 0\]Now we can use the fact that \[(0,0,k_1)\]\[(0,n,k_2)\]\[(n,0,k_3)\]\[(n,n,k_4)\]all lie on the plane, to get that the plane if only defined iff \[k_1+k_3 = k_2+k_4\]So since $k_i \le n$, by doing casework on the sum, we get an answer of \[2\sum_{i = 1}^{n} i^2+(n+1)^2 = \boxed{\frac{1}{3}(2n^3+6n^2+7n+3)}\]

0 MOHS!!! If the tallest leg is $k_1$, then the distance between $k_4$ and $k_2$ from $k_1$ must be equal. Furthermore, this distance is half the distance from $k_3$ to $k_1$ (we are talking vertical distance here of course). Therefore we need $k_1+k_3=k_2+k_4$. If this common value is $0$, we have $0^2$. If it is $1$, we have $1^2$. Continue this casework to obtain the answer of: $$1^2+2^2+ \dots + n^2 + (n+1)^2 + n^2 + \dots + 1^2 = \frac{2n^3+6 n^2+7n+3}{3}$$