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 "2020 CIME I Problems/Problem 1"
m (→‎Solution 2)
 
(6 intermediate revisions by 2 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
Let <math>A</math> denote a move of <math>2</math> units north and <math>1</math> unit east, and let <math>B</math> denote a move of <math>1</math> unit north and <math>2</math> units east. To get to the point <math>(15,15)</math> using only these moves, say <math>x</math> moves in direction <math>A</math> and <math>y</math> moves in direction <math>B</math>, we must have <math>2x+1y=1x+2y=15</math> because both the <math>x</math> and <math>y</math>-coordinates have increased by <math>15</math> since the knight started. Solving this system of equations gives us <math>x=y=5</math>. This means we need the knight to make <math>10</math> moves, <math>5</math> of which are headed in direction <math>A</math>, and the remaining <math>5</math> are headed in direction <math>B</math>. Any combination of these moves work, so the answer is <math>\binom{10}{5}=\boxed{252}.</math>
+
Let <math>A</math> denote a move of <math>2</math> units north and <math>1</math> unit east, and let <math>B</math> denote a move of <math>1</math> unit north and <math>2</math> units east. To get to the point <math>(15,15)</math> using only these moves, say <math>a</math> moves in direction <math>A</math> and <math>b</math> moves in direction <math>B</math>, we must have <math>2a+1b=1a+2b=15</math> because both the <math>x</math>- and <math>y</math>-coordinates have increased by <math>15</math> since the knight started. Solving this system of equations gives us <math>a=b=5</math>. This means we need the knight to make <math>10</math> moves, <math>5</math> of which are headed in direction <math>A</math>, and the remaining <math>5</math> are headed in direction <math>B</math>. Any combination of these moves work, so the answer is <math>\binom{10}{5}=\boxed{252}.</math>
  
 +
==Solution 2==
 +
We can draw lines using <math>(x+1,y+2)</math> and <math>(x+2,y+1)</math>. Calculating the lines, we see that they are from <math>y=2x</math> and <math>y=\frac{1}{2}x</math> respectively. The point <math>(15,15)</math> is on the line <math>y=x</math>, which is in the "middle" between both, since by multiplying or dividing the slope by <math>2</math> we can get the other two lines. This means to get to <math>(15,15)</math>, for every <math>(x+1,y+2)</math> we do, we do one <math>(x+2,y+1)</math> to balance it. Call this system of moves <math>x</math>, and by performing <math>x</math> once, we get to <math>(3,3)</math>.
 +
If we repeat <math>x</math> five more times, we get to <math>(15,15)</math>. Thus this is now a word arrangement problem where we have to arrange five <math>A</math>s and <math>B</math>s which represent each move (letter name is arbitrary). We get <math>\frac{10!}{5!5!}=\boxed{252}.</math>
 +
 +
~ neeyakkid23
 +
 +
==Video Solution==
 +
https://www.youtube.com/watch?v=SFVt0JYLkHY
 +
~Shreyas S
 +
 +
==See also==
 
{{CIME box|year=2020|n=I|before=First Question|num-a=2}}
 
{{CIME box|year=2020|n=I|before=First Question|num-a=2}}
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
−
{{CMC Notice}}
+
{{MAC Notice}}

Latest revision as of 16:40, 2 October 2024

Problem 1

A knight begins on the point $(0,0)$ in the coordinate plane. From any point $(x,y)$ the knight moves to either $(x+2,y+1)$ or $(x+1,y+2)$. Find the number of ways the knight can reach the point $(15,15)$.

Solution

Let $A$ denote a move of $2$ units north and $1$ unit east, and let $B$ denote a move of $1$ unit north and $2$ units east. To get to the point $(15,15)$ using only these moves, say $a$ moves in direction $A$ and $b$ moves in direction $B$, we must have $2a+1b=1a+2b=15$ because both the $x$- and $y$-coordinates have increased by $15$ since the knight started. Solving this system of equations gives us $a=b=5$. This means we need the knight to make $10$ moves, $5$ of which are headed in direction $A$, and the remaining $5$ are headed in direction $B$. Any combination of these moves work, so the answer is $\binom{10}{5}=\boxed{252}.$

Solution 2

We can draw lines using $(x+1,y+2)$ and $(x+2,y+1)$. Calculating the lines, we see that they are from $y=2x$ and $y=\frac{1}{2}x$ respectively. The point $(15,15)$ is on the line $y=x$, which is in the "middle" between both, since by multiplying or dividing the slope by $2$ we can get the other two lines. This means to get to $(15,15)$, for every $(x+1,y+2)$ we do, we do one $(x+2,y+1)$ to balance it. Call this system of moves $x$, and by performing $x$ once, we get to $(3,3)$. If we repeat $x$ five more times, we get to $(15,15)$. Thus this is now a word arrangement problem where we have to arrange five $A$s and $B$s which represent each move (letter name is arbitrary). We get $\frac{10!}{5!5!}=\boxed{252}.$

~ neeyakkid23

Video Solution

https://www.youtube.com/watch?v=SFVt0JYLkHY ~Shreyas S

See also

2020 CIME I (Problems • Answer Key • Resources)
Preceded by
First Question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All CIME Problems and Solutions

The problems on this page are copyrighted by the MAC's Christmas Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_CIME_I_Problems/Problem_1&oldid=228815"