Difference between revisions of "2015 AIME II Problems/Problem 5"
(→Solution) |
(→Solution 3) |
||
(10 intermediate revisions by 4 users not shown) | |||
Line 3: | Line 3: | ||
Two unit squares are selected at random without replacement from an <math>n \times n</math> grid of unit squares. Find the least positive integer <math>n</math> such that the probability that the two selected unit squares are horizontally or vertically adjacent is less than <math>\frac{1}{2015}</math>. | Two unit squares are selected at random without replacement from an <math>n \times n</math> grid of unit squares. Find the least positive integer <math>n</math> such that the probability that the two selected unit squares are horizontally or vertically adjacent is less than <math>\frac{1}{2015}</math>. | ||
− | ==Solution== | + | ==Solution 1== |
− | Call the given grid "Grid A". Consider Grid B, where the vertices of Grid B fall in the centers of the squares of Grid A; thus, Grid B has dimensions <math>(n-1) \times (n-1)</math>. There is a one-to-one correspondence between the edges of Grid B and the number of adjacent pairs of unit squares in Grid A. The number of edges in Grid | + | Call the given grid "Grid A". Consider Grid B, where the vertices of Grid B fall in the centers of the squares of Grid A; thus, Grid B has dimensions <math>(n-1) \times (n-1)</math>. There is a one-to-one correspondence between the edges of Grid B and the number of adjacent pairs of unit squares in Grid A. The number of edges in Grid B is <math>2n(n-1)</math>, and the number of ways to pick two squares out of Grid A is <math>\dbinom{n^2}{2}</math>. So, the probability that the two chosen squares are adjacent is <math>\frac{2n(n-1)}{\binom{n^2}{2}} = \frac{2n(n-1)}{\frac{n^2(n^2-1)}{2}} = \frac{4}{n(n+1)}</math>. We wish to find the smallest positive integer <math>n</math> such that <math>\frac{4}{n(n+1)} < \frac{1}{2015}</math>, and by inspection the first such <math>n</math> is <math>\boxed{090}</math>. |
+ | |||
+ | |||
+ | ==Solution 2== | ||
+ | Consider a <math>3 \times 3</math> grid, where there are <math>4</math> corner squares, <math>4</math> edge squares, and <math>1</math> center square. A <math>4 \times 4</math> grid has <math>4</math> corner squares, <math>8</math> edge squares, and <math>4</math> center squares. By examining simple cases, we can conclude that for a grid that is <math>n \times n</math>, there are always <math>4</math> corners squares, <math>4(n-2)</math> edge squares, and <math>n^2-4n+4</math> center squares. | ||
+ | |||
+ | Each corner square is adjacent to <math>2</math> other squares, edge squares to <math>3</math> other squares, and center squares to <math>4</math> other squares. In the problem, the second square can be any square that is not the first, which means there are <math>n^2-1</math> to choose from. With this information, we can conclude that the probability that second unit square is adjacent to the first is <math>\frac{2}{n^2-1}(\frac{4}{n^2}) +\frac{3}{n^2-1}(\frac{4(n-2)}{n^2}) +\frac{4}{n^2-1}(\frac{n^2-4n+4}{n^2})</math>. | ||
+ | |||
+ | Simplifying, we get <math>\frac{4}{n(n+1)}</math> which we can set to be less than <math>\frac{1}{2015}</math>. By inspection, we find that the first such <math>n</math> is <math>\boxed{090}</math>. | ||
+ | |||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | There are 3 cases in this problem. Number one, the center squares. Two, the edges, and three, the corners. The probability of getting one center square and an adjacent square is <math>\frac{(n-2)(n-2)}{n^2}</math> multiplied by <math>\frac{4}{n^2 -1}</math>. Add that to the probability of an edge and an adjacent square( <math>\frac{4n-8}{n^2}</math> multiplied by <math>\frac{3}{n^2-1} </math>) and the probability of a corner and an adjacent square( <math>\frac{4}{n^2} </math> multiplied by <math>\frac{2}{n^2-1} </math>) to get <math>\frac{4n^2-4n}{n^4-n^2} </math>. Simplify to get <math>\frac{4}{n^2+n} </math>. With some experimentation, we realize that the smallest value of n is <math>\boxed{090}</math>. | ||
+ | |||
+ | |||
+ | ==Solution 4 (cheese)== | ||
+ | |||
+ | Notice how a chosen unit square on the grid has 4 vertically & horizontally adjacent squares around it (not counting corners or sides.) That's <math>\frac{4}{n^2}</math>. Using this, we rewrite <math>\frac{1}{2015}</math> as <math>\frac{4}{8060}</math>. Notice that the denominator <math>8060</math> is really close to <math>90^2</math>, and the problem is asking for the least positive integer less than <math>\frac{1}{2015}</math>. Therefore, the closest possible estimation is <math>\boxed{090}</math>. We can check this by adding in our corners and sides. Easy multiplication and simplification finds us with <math>\boxed{090}</math> as the correct answer. | ||
+ | |||
+ | ~[[OrenSH|orenbad]] | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://www.youtube.com/watch?v=9re2qLzOKWk&t=304s | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
==See also== | ==See also== | ||
{{AIME box|year=2015|n=II|num-b=4|num-a=6}} | {{AIME box|year=2015|n=II|num-b=4|num-a=6}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 17:40, 1 July 2023
Contents
Problem
Two unit squares are selected at random without replacement from an grid of unit squares. Find the least positive integer
such that the probability that the two selected unit squares are horizontally or vertically adjacent is less than
.
Solution 1
Call the given grid "Grid A". Consider Grid B, where the vertices of Grid B fall in the centers of the squares of Grid A; thus, Grid B has dimensions . There is a one-to-one correspondence between the edges of Grid B and the number of adjacent pairs of unit squares in Grid A. The number of edges in Grid B is
, and the number of ways to pick two squares out of Grid A is
. So, the probability that the two chosen squares are adjacent is
. We wish to find the smallest positive integer
such that
, and by inspection the first such
is
.
Solution 2
Consider a grid, where there are
corner squares,
edge squares, and
center square. A
grid has
corner squares,
edge squares, and
center squares. By examining simple cases, we can conclude that for a grid that is
, there are always
corners squares,
edge squares, and
center squares.
Each corner square is adjacent to other squares, edge squares to
other squares, and center squares to
other squares. In the problem, the second square can be any square that is not the first, which means there are
to choose from. With this information, we can conclude that the probability that second unit square is adjacent to the first is
.
Simplifying, we get which we can set to be less than
. By inspection, we find that the first such
is
.
Solution 3
There are 3 cases in this problem. Number one, the center squares. Two, the edges, and three, the corners. The probability of getting one center square and an adjacent square is multiplied by
. Add that to the probability of an edge and an adjacent square(
multiplied by
) and the probability of a corner and an adjacent square(
multiplied by
) to get
. Simplify to get
. With some experimentation, we realize that the smallest value of n is
.
Solution 4 (cheese)
Notice how a chosen unit square on the grid has 4 vertically & horizontally adjacent squares around it (not counting corners or sides.) That's . Using this, we rewrite
as
. Notice that the denominator
is really close to
, and the problem is asking for the least positive integer less than
. Therefore, the closest possible estimation is
. We can check this by adding in our corners and sides. Easy multiplication and simplification finds us with
as the correct answer.
Video Solution
https://www.youtube.com/watch?v=9re2qLzOKWk&t=304s
~MathProblemSolvingSkills.com
See also
2015 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
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.