Difference between revisions of "2005 USAMO Problems/Problem 4"
m (→Solution 1) |
|||
(5 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | =Problem= | + | == 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_2, k_3, k_4)</math> of nonnegative integers can we cut a piece of length <math>k_i</math> from the end of leg <math>L_i \; (i = 1,2,3,4)</math> and still have a stable table? | + | (''Elgin Johnston'') 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_2, k_3, k_4)</math> of nonnegative integers can we cut a piece of length <math>k_i</math> from the end of leg <math>L_i \; (i = 1,2,3,4)</math> 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.) | (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= | + | == Solutions == |
− | ==Solution 1== | + | |
+ | == Solution 1 == | ||
+ | First flip the table upside down and observe the plane that the ends of the legs form. Let this plane be <math>ax+by+c=z</math>. Assume WLOG that the table is the square with endpoints <math>(0,0), (0,1), (1,0), (1,1)</math> on the xy plane. Thus the lengths of the legs will be <math>c, c+b, c+a, c+a+b</math> respectively. In other words <math>k_1+k_3=k_2+k_4=x</math> for some <math>0 \le x \le 2n</math>. | ||
+ | |||
+ | For <math>0 \le x \le n</math>, it is easy to see that the number of stable tables is <math>(x+1)^2</math>. | ||
+ | |||
+ | For <math>n+1 \le x \le 2n</math>, we can biject the stable tables of <math>x</math> to the stable of <math>2n-x</math> by replacing all of the legs with the cut off portions. | ||
+ | |||
+ | So the total number of stable tables is <math>1^2+2^2+...+n^2+(n+1)^2+n^2+...+2^2+1^2 =</math> <math>(1^2+2^2+...+(n+1)^2)+(1^2+2^2+...+n^2) =</math> <math>\dfrac{(n+1)(n+2)(2n+3)}{6}+\dfrac{n(n+1)(2n+1)}{6}=\boxed{\dfrac{2n^3+6n^2+7n+3}{3}}</math>. | ||
+ | |||
+ | |||
+ | === Solution 2 === | ||
Let <math>C_i</math> be the number of sets of cuts <math>\{k_1,k_2,k_3,k_4\}</math> that result in the longest leg being of length <math>i</math>. Then <math>C_i=C_{i-1}+x</math>, and we will evaluate <math>x</math> to develop a recursion. Note that if a set of cuts has non-zero cuts, then if that set is counted in <math>C_i</math>, subtract <math>1</math> from each of the cuts to obtain a set of cuts that is counted in <math>C_{i-1}</math>. For example, if <math>\{2,3,4,5\}</math> was counted in <math>C_5</math>, then <math>\{1,2,3,4\}</math> would have been counted in <math>C_4</math> because subtracting the same length from each leg preserves the quality of the legs being coplanar, and there is a bijection. | Let <math>C_i</math> be the number of sets of cuts <math>\{k_1,k_2,k_3,k_4\}</math> that result in the longest leg being of length <math>i</math>. Then <math>C_i=C_{i-1}+x</math>, and we will evaluate <math>x</math> to develop a recursion. Note that if a set of cuts has non-zero cuts, then if that set is counted in <math>C_i</math>, subtract <math>1</math> from each of the cuts to obtain a set of cuts that is counted in <math>C_{i-1}</math>. For example, if <math>\{2,3,4,5\}</math> was counted in <math>C_5</math>, then <math>\{1,2,3,4\}</math> would have been counted in <math>C_4</math> because subtracting the same length from each leg preserves the quality of the legs being coplanar, and there is a bijection. | ||
Line 12: | Line 23: | ||
This final equation is easy to analyze. Simply use <math>G(x)</math> as the first term of a geometric series with constant multiplier of <math>x</math>. This gives <math>C_i=2i^2+2i+1</math>. The total number of sets of cuts for a table of legs of length <math>n</math> is the sum of all the <math>C_i</math>, <math>0\le i\le n</math>, from which we deduce the answer <math>\frac{2n^3 + 6n^2 +7n + 3}{3}</math>, or <math>\frac{(n+1)(2n^2 + 4n +3)}{3}</math>. | This final equation is easy to analyze. Simply use <math>G(x)</math> as the first term of a geometric series with constant multiplier of <math>x</math>. This gives <math>C_i=2i^2+2i+1</math>. The total number of sets of cuts for a table of legs of length <math>n</math> is the sum of all the <math>C_i</math>, <math>0\le i\le n</math>, from which we deduce the answer <math>\frac{2n^3 + 6n^2 +7n + 3}{3}</math>, or <math>\frac{(n+1)(2n^2 + 4n +3)}{3}</math>. | ||
− | ==Solution | + | |
+ | === Solution 3 === | ||
The problem's condition is that the ends of the legs must be coplanar. So the plane formed by legs <math>L_1</math>, <math>L_2</math>, and <math>L_3</math> is the same as the plane formed by the legs <math>L_2</math>, <math>L_3</math>, and <math>L_4</math> iff the problem's condition is met. | The problem's condition is that the ends of the legs must be coplanar. So the plane formed by legs <math>L_1</math>, <math>L_2</math>, and <math>L_3</math> is the same as the plane formed by the legs <math>L_2</math>, <math>L_3</math>, and <math>L_4</math> iff the problem's condition is met. | ||
Line 22: | Line 34: | ||
The number of possible 4-tuples <math>(k_1,k_2,k_3,k_4)</math> is thus <math>1^2+2^2+...+n^2+(n+1)^2+n^2+...+2^2+1^2</math>, which is equivalent to <math>(1^2+2^2+...+(n+1)^2)+(1^2+2^2+...+n^2)</math>. Our final answer is <math>\dfrac{(n+1)(n+2)(2n+3)}{6}+\dfrac{n(n+1)(2n+1)}{6}=\boxed{\dfrac{2n^3+6n^2+7n+3}{3}}</math>. | The number of possible 4-tuples <math>(k_1,k_2,k_3,k_4)</math> is thus <math>1^2+2^2+...+n^2+(n+1)^2+n^2+...+2^2+1^2</math>, which is equivalent to <math>(1^2+2^2+...+(n+1)^2)+(1^2+2^2+...+n^2)</math>. Our final answer is <math>\dfrac{(n+1)(n+2)(2n+3)}{6}+\dfrac{n(n+1)(2n+1)}{6}=\boxed{\dfrac{2n^3+6n^2+7n+3}{3}}</math>. | ||
+ | |||
+ | |||
+ | {{alternate solutions}} | ||
== See Also== | == See Also== | ||
{{USAMO newbox|year=2005|num-b=3|num-a=5}} | {{USAMO newbox|year=2005|num-b=3|num-a=5}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 20:51, 6 January 2024
Problem
(Elgin Johnston) Legs of a square table each have length
, where
is a positive integer. For how many ordered 4-tuples
of nonnegative integers can we cut a piece of length
from the end of leg
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
First flip the table upside down and observe the plane that the ends of the legs form. Let this plane be . Assume WLOG that the table is the square with endpoints
on the xy plane. Thus the lengths of the legs will be
respectively. In other words
for some
.
For , it is easy to see that the number of stable tables is
.
For , we can biject the stable tables of
to the stable of
by replacing all of the legs with the cut off portions.
So the total number of stable tables is
.
Solution 2
Let be the number of sets of cuts
that result in the longest leg being of length
. Then
, and we will evaluate
to develop a recursion. Note that if a set of cuts has non-zero cuts, then if that set is counted in
, subtract
from each of the cuts to obtain a set of cuts that is counted in
. For example, if
was counted in
, then
would have been counted in
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 If the remaining legs have length
and
, then
, so
options. The initial corner can be any of the four legs, but each of the four permutations of the set of cuts
is repeated twice, so we have
total additional sets of cuts. We conclude that
, and note that
. Now we can create generating functions.
. Also,
. From the recursion, we have
This final equation is easy to analyze. Simply use
as the first term of a geometric series with constant multiplier of
. This gives
. The total number of sets of cuts for a table of legs of length
is the sum of all the
,
, from which we deduce the answer
, or
.
Solution 3
The problem's condition is that the ends of the legs must be coplanar. So the plane formed by legs ,
, and
is the same as the plane formed by the legs
,
, and
iff the problem's condition is met.
We now assign coordinates to the ends of the legs. Let the table be on the xy-plane such that is at
,
is at
,
is at
, and
is at
, where
is the side length of the table. (Note that we have turned the table over so that the top lies on the xy plane while the legs point in the +z direction - this does not affect the result.) A plane in 3-space has the equation form
. Plugging the coordinates of
,
, and
into
, we eventually get
,
,
. Plugging the coordinates of
,
, and
into
, we get
,
,
.
Since we need these to be coplanar, we set ,
, and
. (Notice that the
's cancel.) From
, we get
[1]. From
, we get
[2]. From
, we get
[3]. Notice that [1] and [2] can both be obtained directly from [3] and are therefore redundant. The only condition we have left to ensure that the ends of the legs are coplanar is
. Let
.
We proceed using casework by .
is an integer between
and
, inclusive. Furthermore, we note that
range from
to
, inclusive. For
, each of
and
have one choice,
. For
, they each have two choices,
and
. And so on, until
, where they each have
choices:
. When
, the restriction that
takes effect: there are only
choices for each ordered pair, which are
. And so on, until
, where there is one choice for each ordered pair,
.
The number of possible 4-tuples is thus
, which is equivalent to
. Our final answer is
.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See Also
2005 USAMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.