Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2005 USAMO Problems/Problem 4"

(New page: =Problem= Legs <math>L_1, L_2, L_3, L_4</math> of a square table each have length <math>n</math>, where <math>n</math> is a positive integer. For how many ordered 4-tuples <math>(k_1, k...)
(No difference)

Revision as of 18:32, 17 October 2008

Problem

Legs $L_1, L_2, L_3, L_4$ of a square table each have length $n$, where $n$ is a positive integer. For how many ordered 4-tuples $(k_1, k_2, k_3, k_4)$ of nonnegative integers can we cut a piece of length $k_i$ from the end of leg $L_i \; (i = 1,2,3,4)$ and still have a stable table?

(The table is stable if it can be placed so that all four of the leg ends touch the floor. Note that a cut leg of length 0 is permitted.)

Solutions

Solution 1

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$, then $(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_ix^i$. Also, $G(x)=\sum_{i=1}^\infty 4ix^i$. 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}$, or $\frac{(n+1)(2n^2 + 4n +3}{3}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_USAMO_Problems/Problem_4&oldid=28211"