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 AIME I Problems/Problem 13"

 
m (→‎Solution 2)
 
(18 intermediate revisions by 12 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
A particle moves in the Cartesian Plane according to the following rules:
+
A particle moves in the [[Cartesian plane]] according to the following rules:
  
 
# From any lattice point <math> (a,b), </math> the particle may only move to <math> (a+1,b), (a,b+1), </math> or <math>(a+1,b+1). </math>
 
# From any lattice point <math> (a,b), </math> the particle may only move to <math> (a+1,b), (a,b+1), </math> or <math>(a+1,b+1). </math>
Line 6: Line 6:
  
 
How many different paths can the particle take from <math> (0,0) </math> to <math> (5,5) </math>?
 
How many different paths can the particle take from <math> (0,0) </math> to <math> (5,5) </math>?
 +
 +
__TOC__
  
 
== Solution ==
 
== Solution ==
 +
=== Solution 1 ===
 +
The length of the path (the number of times the particle moves) can range from <math>l = 5</math> to <math>9</math>; notice that <math>d = 10-l</math> gives the number of diagonals. Let <math>R</math> represent a move to the right, <math>U</math> represent a move upwards, and <math>D</math> to be a move that is diagonal. [[Casework]] upon the number of diagonal moves:
 +
 +
*'''Case ''' <math>d = 1</math>: It is easy to see only <math>2</math> cases.
 +
*'''Case ''' <math>d = 2</math>: There are two diagonals. We need to generate a string with <math>3</math> <math>R</math>'s, <math>3</math> <math>U</math>'s, and <math>2</math> <math>D</math>'s such that no two <math>R</math>'s or <math>U</math>'s are adjacent. The <math>D</math>'s split the string into three sections (<math>-D-D-</math>): by the [[Pigeonhole principle]] all of at least one of the two letters must be all together (i.e., stay in a row).
 +
:If both <math>R</math> and <math>U</math> stay together, then there are <math>3 \cdot 2=6</math> ways.
 +
:If either <math>R</math> or <math>U</math> splits, then there are <math>3</math> places to put the letter that splits, which has <math>2</math> possibilities. The remaining letter must divide into <math>2</math> in one section and <math>1</math> in the next, giving <math>2</math> ways. This totals <math>6 + 3\cdot 2\cdot 2 = 18</math> ways.
 +
*'''Case ''' <math>d = 3</math>: Now <math>2</math> <math>R</math>'s, <math>2</math> <math>U</math>'s, and <math>3</math> <math>D</math>'s, so the string is divided into <math>4</math> partitions (<math>-D-D-D-</math>).
 +
:If the <math>R</math>'s and <math>U</math>'s stay together, then there are <math>4 \cdot 3 = 12</math> places to put them.
 +
:If one of them splits and the other stays together, then there are <math>4 \cdot {3\choose 2}</math> places to put them, and <math>2</math> ways to pick which splits, giving <math>4 \cdot 3 \cdot 2 = 24</math> ways.
 +
:If both groups split, then there are <math>{4\choose 2}=6</math> ways to arrange them. These add up to <math>12 + 24 + 6 = 42</math> ways.
 +
*'''Case ''' <math>d = 4</math>: Now <math>1</math> <math>R</math>, <math>1</math> <math>U</math>, <math>4</math> <math>D</math>'s (<math>-D-D-D-D-</math>). There are <math>5</math> places to put <math>R</math>, <math>4</math> places to put <math>U</math>, giving <math>20</math> ways.
 +
*'''Case ''' <math>d = 5</math>: It is easy to see only <math>1</math> case.
 +
 +
Together, these add up to <math>2 + 18 + 42 + 20 + 1 = \boxed{083}</math>.
 +
 +
=== Solution 2 ===
 +
Another possibility is to use block-walking and [[recursion]]: for each vertex, the number of ways to reach it is <math>a + b + c</math>, where <math>a</math> is the number of ways to reach the vertex from the left (without having come to ''that'' vertex (the one on the left) from below), <math>b</math> is the number of ways to reach the vertex from the vertex diagonally down and left, and <math>c</math> is the number of ways to reach the vertex from below (without having come to ''that'' vertex (the one below) from the left).
 +
 +
Assign to each point <math>(i,j)</math> the triplet <math>(a_{i,j}, b_{i,j}, c_{i,j})</math>. Let <math>s(i,j) = a_{i,j}+ b_{i,j}+ c_{i,j}</math>. Let all lattice points that contain exactly one negative coordinate be assigned to <math>(0,0,0)</math>. This leaves the lattice points of the first quadrant, the positive parts of the <math>x</math> and <math>y</math> axes, and the origin unassigned. As a seed, assign to <math>(0,1,0)</math>. (We will see how this correlates with the problem.) Then define for each lattice point <math>(i,j)</math> its triplet thus:
 +
<cmath>\begin{align*}
 +
a_{i,j} &= s(i-1,j) - c_{i-1,j}\\
 +
b_{i,j} &= s(i-1,j-1) \\
 +
c_{i,j} &= s(i,j-1) - a_{i,j-1}.
 +
\end{align*}</cmath>
 +
It is evident that <math>s(i,j)</math> is the number of ways to reach <math>(i,j)</math> from <math>(0,0)</math>. Therefore we compute vertex by vertex the triplets <math>(a_{i,j}, b_{i,j}, c_{i,j})</math> with <math>0 \leq i, j \leq 5</math>.
 +
<asy>
 +
defaultpen(fontsize(8)+0.8+heavyblue); size(250);
 +
 +
for(int i = 0; i<6; ++i) { draw((0,i)--(5,i)^^(i,0)--(i,5), gray+0.25); }
 +
label("$(0,0,0)$", (0,0), N);
 +
for(int i = 1; i<6; ++i) { label("$(0,0,1)$", (0,i), N); label("$(1,0,0)$", (i,0), N); label("$({"+string(i-1)+"},1,0)$", (i,1), N); label("$(0,1,{"+string(i-1)+"})$", (1,i), N);}
 +
real[] val={1,2,4,7};
 +
for(int i = 2; i<6; ++i) { label("$(1,{"+string(i-1)+"}, {"+string(val[i-2])+"})$", (2,i), N); label("$({"+string(val[i-2])+"},{"+string(i-1)+"}, 1)$", (i,2), N);}
 +
 +
label("$(3,3,3)$", (3,3), N); label("$(9,9,9)$", (4,4), N); label("$(28,27,28)$", (5,5), N);
 +
label("$(4,5,6)$", (3,4), N); label("$(6,5,4)$", (4,3), N);
 +
label("$(5,8,11)$", (3,5), N); label("$(11,8,5)$", (5,3), N);
 +
label("$(13,15,18)$", (4,5), N); label("$(18,15,13)$", (5,4), N);
 +
</asy>
 +
Finally, after simple but tedious calculations, we find that <math>(a_{5,5}, b_{5,5}, c_{5,5}) = (28,27,28)</math>, so <math>s(i,j)=28+27+28 = \boxed{083}</math>.
  
 
== See also ==
 
== See also ==
−
* [[2005 AIME I Problems]]
+
{{AIME box|year=2005|n=I|num-b=12|num-a=14}}
 +
 
 +
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 23:21, 28 July 2022

Problem

A particle moves in the Cartesian plane according to the following rules:

  1. From any lattice point $(a,b),$ the particle may only move to $(a+1,b), (a,b+1),$ or $(a+1,b+1).$
  2. There are no right angle turns in the particle's path.

How many different paths can the particle take from $(0,0)$ to $(5,5)$?

Solution

Solution 1

The length of the path (the number of times the particle moves) can range from $l = 5$ to $9$; notice that $d = 10-l$ gives the number of diagonals. Let $R$ represent a move to the right, $U$ represent a move upwards, and $D$ to be a move that is diagonal. Casework upon the number of diagonal moves:

  • Case $d = 1$: It is easy to see only $2$ cases.
  • Case $d = 2$: There are two diagonals. We need to generate a string with $3$ $R$'s, $3$ $U$'s, and $2$ $D$'s such that no two $R$'s or $U$'s are adjacent. The $D$'s split the string into three sections ($-D-D-$): by the Pigeonhole principle all of at least one of the two letters must be all together (i.e., stay in a row).
If both $R$ and $U$ stay together, then there are $3 \cdot 2=6$ ways.
If either $R$ or $U$ splits, then there are $3$ places to put the letter that splits, which has $2$ possibilities. The remaining letter must divide into $2$ in one section and $1$ in the next, giving $2$ ways. This totals $6 + 3\cdot 2\cdot 2 = 18$ ways.
  • Case $d = 3$: Now $2$ $R$'s, $2$ $U$'s, and $3$ $D$'s, so the string is divided into $4$ partitions ($-D-D-D-$).
If the $R$'s and $U$'s stay together, then there are $4 \cdot 3 = 12$ places to put them.
If one of them splits and the other stays together, then there are $4 \cdot {3\choose 2}$ places to put them, and $2$ ways to pick which splits, giving $4 \cdot 3 \cdot 2 = 24$ ways.
If both groups split, then there are ${4\choose 2}=6$ ways to arrange them. These add up to $12 + 24 + 6 = 42$ ways.
  • Case $d = 4$: Now $1$ $R$, $1$ $U$, $4$ $D$'s ($-D-D-D-D-$). There are $5$ places to put $R$, $4$ places to put $U$, giving $20$ ways.
  • Case $d = 5$: It is easy to see only $1$ case.

Together, these add up to $2 + 18 + 42 + 20 + 1 = \boxed{083}$.

Solution 2

Another possibility is to use block-walking and recursion: for each vertex, the number of ways to reach it is $a + b + c$, where $a$ is the number of ways to reach the vertex from the left (without having come to that vertex (the one on the left) from below), $b$ is the number of ways to reach the vertex from the vertex diagonally down and left, and $c$ is the number of ways to reach the vertex from below (without having come to that vertex (the one below) from the left).

Assign to each point $(i,j)$ the triplet $(a_{i,j}, b_{i,j}, c_{i,j})$. Let $s(i,j) = a_{i,j}+ b_{i,j}+ c_{i,j}$. Let all lattice points that contain exactly one negative coordinate be assigned to $(0,0,0)$. This leaves the lattice points of the first quadrant, the positive parts of the $x$ and $y$ axes, and the origin unassigned. As a seed, assign to $(0,1,0)$. (We will see how this correlates with the problem.) Then define for each lattice point $(i,j)$ its triplet thus: \begin{align*} a_{i,j} &= s(i-1,j) - c_{i-1,j}\\ b_{i,j} &= s(i-1,j-1) \\ c_{i,j} &= s(i,j-1) - a_{i,j-1}. \end{align*} It is evident that $s(i,j)$ is the number of ways to reach $(i,j)$ from $(0,0)$. Therefore we compute vertex by vertex the triplets $(a_{i,j}, b_{i,j}, c_{i,j})$ with $0 \leq i, j \leq 5$. [asy] defaultpen(fontsize(8)+0.8+heavyblue); size(250); for(int i = 0; i<6; ++i) { draw((0,i)--(5,i)^^(i,0)--(i,5), gray+0.25); } label("$(0,0,0)$", (0,0), N); for(int i = 1; i<6; ++i) { label("$(0,0,1)$", (0,i), N); label("$(1,0,0)$", (i,0), N); label("$({"+string(i-1)+"},1,0)$", (i,1), N); label("$(0,1,{"+string(i-1)+"})$", (1,i), N);} real[] val={1,2,4,7}; for(int i = 2; i<6; ++i) { label("$(1,{"+string(i-1)+"}, {"+string(val[i-2])+"})$", (2,i), N); label("$({"+string(val[i-2])+"},{"+string(i-1)+"}, 1)$", (i,2), N);} label("$(3,3,3)$", (3,3), N); label("$(9,9,9)$", (4,4), N); label("$(28,27,28)$", (5,5), N); label("$(4,5,6)$", (3,4), N); label("$(6,5,4)$", (4,3), N); label("$(5,8,11)$", (3,5), N); label("$(11,8,5)$", (5,3), N); label("$(13,15,18)$", (4,5), N); label("$(18,15,13)$", (5,4), N); [/asy] Finally, after simple but tedious calculations, we find that $(a_{5,5}, b_{5,5}, c_{5,5}) = (28,27,28)$, so $s(i,j)=28+27+28 = \boxed{083}$.

See also

2005 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_AIME_I_Problems/Problem_13&oldid=176348"