Difference between revisions of "1996 AIME Problems/Problem 14"
m |
m (→Solution 2) |
||
(12 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | + | A <math>150\times 324\times 375</math> [[rectangle|rectangular]] [[solid]] is made by gluing together <math>1\times 1\times 1</math> cubes. An internal [[diagonal]] of this solid passes through the interiors of how many of the <math>1\times 1\times 1</math> [[cube (geometry) | cube]]s? | |
+ | |||
== Solution == | == Solution == | ||
− | + | === Solution 1 === | |
Place one corner of the solid at <math>(0,0,0)</math> and let <math>(a,b,c)</math> be the general coordinates of the diagonally opposite corner of the rectangle, where <math>a, b, c \in \mathbb{Z_{+}}</math>. | Place one corner of the solid at <math>(0,0,0)</math> and let <math>(a,b,c)</math> be the general coordinates of the diagonally opposite corner of the rectangle, where <math>a, b, c \in \mathbb{Z_{+}}</math>. | ||
− | We consider the vector equation of the diagonal segment represented by: | + | We consider the [[vector]] equation of the diagonal segment represented by: |
<math>(x, y, z) =m (a, b, c)</math>, where <math>m \in \mathbb{R}, 0 < m \le 1</math>. | <math>(x, y, z) =m (a, b, c)</math>, where <math>m \in \mathbb{R}, 0 < m \le 1</math>. | ||
Consider a point on the diagonal with coordinates <math>(ma, mb, mc)</math>. We have 3 key observations as this point moves from <math>(0,0,0)</math> towards <math>(a,b,c)</math>: | Consider a point on the diagonal with coordinates <math>(ma, mb, mc)</math>. We have 3 key observations as this point moves from <math>(0,0,0)</math> towards <math>(a,b,c)</math>: | ||
− | + | # When exactly one of <math>ma</math>, <math>mb</math>, <math>mc</math> becomes a positive integer, the point crosses one of the [[face]]s of a <math>1 \times 1 \times 1</math> cube from the outside to the inside of the cube. | |
− | + | # When exactly two of <math>ma</math>, <math>mb</math>, <math>mc</math> become positive integers, the point enters a new cube through one of the edges of the cube from the outside to the inside of the cube. | |
+ | |||
+ | # When all three <math>ma</math>, <math>mb</math>, <math>mc</math> become positive integers, the point enters a cube through one of its vertices from the outside to the inside of the cube. | ||
− | |||
The number of cubes the diagonal passes is equal to the number of points on the diagonal that has one or more positive integers as coordinates. | The number of cubes the diagonal passes is equal to the number of points on the diagonal that has one or more positive integers as coordinates. | ||
− | If we slice the | + | If we slice the solid up by the <math>x</math>-planes defined by <math>x=1,2,3,4, \ldots, a</math>, the diagonal will cut these <math>x</math>-planes exactly <math>a</math> times (plane of <math>x=0</math> is not considered since <math>m \ne 0</math>). Similar arguments for slices along <math>y</math>-planes and <math>z</math>-planes give diagonal cuts of <math>b</math>, and <math>c</math> times respectively. The total cuts by the diagonal is therefore <math>a+b+c</math>, if we can ensure that no more than <math>1</math> positive integer is present in the x, y, or z coordinate in all points <math>(ma,mb,mc)</math> on the diagonal. Note that point <math>(a,b,c)</math> is already one such exception. |
− | But for each diagonal point <math>(ma,mb,mc)</math> with 2 (or more) positive | + | But for each diagonal point <math>(ma,mb,mc)</math> with 2 (or more) [[positive]] [[integer]]s occurring at the same time, <math>a+b+c</math> counts the number of cube passes as <math>2</math> instead of <math>1</math> for each such point. There are <math>\gcd(a,b)+\gcd(b,c)+\gcd(c,a)</math> points in such over-counting. We therefore subtract one time such over-counting from <math>a+b+c</math>. |
And for each diagonal point <math>(ma,mb,mc)</math> with exactly <math>3</math> integers occurring at the same time, <math>a+b+c</math> counts the number of cube passes as <math>3</math> instead of <math>1</math>; ie <math>a+b+c</math> over-counts each of such points by <math>2</math>. But since <math>\gcd(a,b)+\gcd(b,c)+\gcd(c,a)</math> already subtracted three times for the case of <math>3</math> integers occurring at the same time (since there are <math>3</math> of these gcd terms that represent all combinations of 3 edges of a cube meeting at a vertex), we have the final count for each such point as <math>1 = 3-3+k \Rightarrow k=1</math>, where <math>k</math> is our correction term. That is, we need to add <math>k=1</math> time <math>\gcd(a,b,c)</math> back to account for the case of 3 simultaneous integers. | And for each diagonal point <math>(ma,mb,mc)</math> with exactly <math>3</math> integers occurring at the same time, <math>a+b+c</math> counts the number of cube passes as <math>3</math> instead of <math>1</math>; ie <math>a+b+c</math> over-counts each of such points by <math>2</math>. But since <math>\gcd(a,b)+\gcd(b,c)+\gcd(c,a)</math> already subtracted three times for the case of <math>3</math> integers occurring at the same time (since there are <math>3</math> of these gcd terms that represent all combinations of 3 edges of a cube meeting at a vertex), we have the final count for each such point as <math>1 = 3-3+k \Rightarrow k=1</math>, where <math>k</math> is our correction term. That is, we need to add <math>k=1</math> time <math>\gcd(a,b,c)</math> back to account for the case of 3 simultaneous integers. | ||
Line 34: | Line 36: | ||
Therefore | Therefore | ||
− | <math>D = 150+324+375-(6+3+75)+3 = 768</math>. | + | <math>D = 150+324+375-(6+3+75)+3 = \boxed{768}</math>. |
+ | |||
+ | === Solution 2 === | ||
+ | Consider a point travelling across the internal diagonal, and let the internal diagonal have a length of <math>d</math>. The point enters a new unit cube in the <math>x,y,z</math> dimensions at multiples of <math>\frac{d}{150}, \frac{d}{324}, \frac{d}{375}</math> respectively. We proceed by using PIE. | ||
+ | |||
+ | The point enters a new cube in the <math>x</math> dimension <math>150</math> times, in the <math>y</math> dimension <math>324</math> times and in the <math>z</math> dimension, <math>375</math> times. | ||
+ | |||
+ | The point enters a new cube in the <math>x</math> and <math>y</math> dimensions whenever a multiple of <math>\frac{d}{150}</math> equals a multiple of <math>\frac{d}{324}</math>. This occurs <math>\gcd(150, 324)</math> times. Similarly, a point enters a new cube in the <math>y,z</math> dimensions <math>\gcd(324, 375)</math> times and a point enters a new cube in the <math>z,x</math> dimensions <math>\gcd(375, 150)</math> times. | ||
+ | |||
+ | The point enters a new cube in the <math>x,y</math> and <math>z</math> dimensions whenever some multiples of <math>\frac{d}{150}, \frac{d}{324}, \frac{d}{375}</math> are equal. This occurs <math>\gcd(150, 324, 375)</math> times. | ||
+ | |||
+ | The total number of unit cubes entered is then | ||
+ | <math>150+324+375-[\gcd(150, 324)+\gcd(324, 375)+\gcd(375, 150)] + \gcd(150, 324, 375) = \boxed{768}</math> | ||
== See also == | == See also == | ||
− | + | {{AIME box|year=1996|num-b=13|num-a=15}} | |
+ | |||
+ | [[Category:Intermediate Geometry Problems]] | ||
+ | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 21:21, 22 September 2023
Problem
A rectangular solid is made by gluing together
cubes. An internal diagonal of this solid passes through the interiors of how many of the
cubes?
Solution
Solution 1
Place one corner of the solid at and let
be the general coordinates of the diagonally opposite corner of the rectangle, where
.
We consider the vector equation of the diagonal segment represented by:
, where
.
Consider a point on the diagonal with coordinates . We have 3 key observations as this point moves from
towards
:
- When exactly one of
,
,
becomes a positive integer, the point crosses one of the faces of a
cube from the outside to the inside of the cube.
- When exactly two of
,
,
become positive integers, the point enters a new cube through one of the edges of the cube from the outside to the inside of the cube.
- When all three
,
,
become positive integers, the point enters a cube through one of its vertices from the outside to the inside of the cube.
The number of cubes the diagonal passes is equal to the number of points on the diagonal that has one or more positive integers as coordinates.
If we slice the solid up by the -planes defined by
, the diagonal will cut these
-planes exactly
times (plane of
is not considered since
). Similar arguments for slices along
-planes and
-planes give diagonal cuts of
, and
times respectively. The total cuts by the diagonal is therefore
, if we can ensure that no more than
positive integer is present in the x, y, or z coordinate in all points
on the diagonal. Note that point
is already one such exception.
But for each diagonal point with 2 (or more) positive integers occurring at the same time,
counts the number of cube passes as
instead of
for each such point. There are
points in such over-counting. We therefore subtract one time such over-counting from
.
And for each diagonal point with exactly
integers occurring at the same time,
counts the number of cube passes as
instead of
; ie
over-counts each of such points by
. But since
already subtracted three times for the case of
integers occurring at the same time (since there are
of these gcd terms that represent all combinations of 3 edges of a cube meeting at a vertex), we have the final count for each such point as
, where
is our correction term. That is, we need to add
time
back to account for the case of 3 simultaneous integers.
Therefore, the total diagonal cube passes is:
.
For , we have:
,
,
,
.
Therefore
.
Solution 2
Consider a point travelling across the internal diagonal, and let the internal diagonal have a length of . The point enters a new unit cube in the
dimensions at multiples of
respectively. We proceed by using PIE.
The point enters a new cube in the dimension
times, in the
dimension
times and in the
dimension,
times.
The point enters a new cube in the and
dimensions whenever a multiple of
equals a multiple of
. This occurs
times. Similarly, a point enters a new cube in the
dimensions
times and a point enters a new cube in the
dimensions
times.
The point enters a new cube in the and
dimensions whenever some multiples of
are equal. This occurs
times.
The total number of unit cubes entered is then
See also
1996 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.