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 "1996 AIME Problems/Problem 14"

 
(→‎Solution)
Line 2: Line 2:
  
 
== Solution ==
 
== Solution ==
 +
 +
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:
 +
<math>(x, y, z) =m (a, b, c)</math>, where <math>m \in \mathbb{R}, 0 \le 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>:
 +
 +
1. The point crosses  one of the faces of a <math>1 \times 1 \times 1</math> cube from the outisde to the inside of the cube, when exactly one of <math>ma</math>, <math>mb</math>, <math>mc</math> becomes a positive integer.
 +
 +
2. 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.
 +
 +
3. 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.
 +
 +
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). 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) postive integers 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 point.  There are <math>\gcd(a,b)+\gcd(b,c)+\gcd(c,a)</math> points in such over-counting. We therefore subtract one time of 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 time 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 3 edges 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 of <math>\gcd(a,b,c)</math> back to account for the case of 3 simultaneous integers.
 +
 +
Therefore, the total diagonal cube passes is:
 +
<math>D = a+b+c-\left[ \gcd(a,b)+\gcd(b,c)+\gcd(c,a) \right]+\gcd(a,b,c)</math>.
 +
 +
For <math>(a,b,c) = (150, 324, 375)</math>, we have:
 +
<math>\gcd(150,324)=6</math>,
 +
<math>\gcd(324,375)=3</math>,
 +
<math>\gcd(150,375)=75</math>,
 +
<math>\gcd(150,324,375)=3</math>.
 +
 +
Therefore
 +
<math>D = 150+324+375-(6+3+75)+3 = 768</math>.
  
 
== See also ==
 
== See also ==
 
* [[1996 AIME Problems]]
 
* [[1996 AIME Problems]]

Revision as of 21:29, 12 August 2006

Problem

Solution

Place one corner of the solid at $(0,0,0)$ and let $(a,b,c)$ be the general coordinates of the diagonally opposite corner of the rectangle, where $a, b, c \in \mathbb{Z_{+}}$.

We consider the vector equation of the diagonal segment represented by: $(x, y, z) =m (a, b, c)$, where $m \in \mathbb{R}, 0 \le m \le 1$.

Consider a point on the diagonal with coordinates $(ma, mb, mc)$. We have 3 key observations as this point moves from $(0,0,0)$ towards $(a,b,c)$:

1. The point crosses one of the faces of a $1 \times 1 \times 1$ cube from the outisde to the inside of the cube, when exactly one of $ma$, $mb$, $mc$ becomes a positive integer.

2. When exactly two of $ma$, $mb$, $mc$ 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.

3. When all three $ma$, $mb$, $mc$ 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 $x$-planes defined by $x=1,2,3,4, \ldots, a$, the diagonal will cut these $x$-planes exactly $a$ times (plane of $x=0$ is not considered). Similar arguments for slices along $y$-planes and $z$-planes give diagonal cuts of $b$, and $c$ times respectively. The total cuts by the diagonal is therefore $a+b+c$, if we can ensure that no more than $1$ positive integer is present in the x, y, or z coordinate in all points $(ma,mb,mc)$ on the diagonal. Note that point $(a,b,c)$ is already one such exception.

But for each diagonal point $(ma,mb,mc)$ with 2 (or more) postive integers occurring at the same time, $a+b+c$ counts the number of cube passes as $2$ instead of $1$ for each point. There are $\gcd(a,b)+\gcd(b,c)+\gcd(c,a)$ points in such over-counting. We therefore subtract one time of such over-counting from $a+b+c$.

And for each diagonal point $(ma,mb,mc)$ with exactly $3$ integers occurring at the same time, $a+b+c$ counts the number of cube passes as $3$ instead of $1$; ie $a+b+c$ over-counts each of such points by $2$. But since $\gcd(a,b)+\gcd(b,c)+\gcd(c,a)$ already subtracted three time for the case of $3$ integers occurring at the same time (since there are $3$ of these gcd terms that represent 3 edges meeting at a vertex), we have the final count for each such point as $1 = 3-3+k \Rightarrow k=1$, where $k$ is our correction term. That is, we need to add $k=1$ time of $\gcd(a,b,c)$ back to account for the case of 3 simultaneous integers.

Therefore, the total diagonal cube passes is: $D = a+b+c-\left[ \gcd(a,b)+\gcd(b,c)+\gcd(c,a) \right]+\gcd(a,b,c)$.

For $(a,b,c) = (150, 324, 375)$, we have: $\gcd(150,324)=6$, $\gcd(324,375)=3$, $\gcd(150,375)=75$, $\gcd(150,324,375)=3$.

Therefore $D = 150+324+375-(6+3+75)+3 = 768$.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_AIME_Problems/Problem_14&oldid=9468"