Difference between revisions of "2020 CIME I Problems/Problem 1"
(Created page with "==Problem 1== A knight begins on the point <math>(0,0)</math> in the coordinate plane. From any point <math>(x,y)</math> the knight moves to either <math>(x+2,y+1)</math> or <...") |
|||
| Line 1: | Line 1: | ||
==Problem 1== | ==Problem 1== | ||
A knight begins on the point <math>(0,0)</math> in the coordinate plane. From any point <math>(x,y)</math> the knight moves to either <math>(x+2,y+1)</math> or <math>(x+1,y+2)</math>. Find the number of ways the knight can reach the point <math>(15,15)</math>. | A knight begins on the point <math>(0,0)</math> in the coordinate plane. From any point <math>(x,y)</math> the knight moves to either <math>(x+2,y+1)</math> or <math>(x+1,y+2)</math>. Find the number of ways the knight can reach the point <math>(15,15)</math>. | ||
| + | |||
| + | ==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> | ||
| + | |||
| + | {{CIME box|year=2020|n=I|before=First Question|num-a=2}} | ||
| + | |||
| + | [[Category:Intermediate Combinatorics Problems]] | ||
| + | {{CMC Notice}} | ||
Revision as of 19:53, 30 August 2020
Problem 1
A knight begins on the point 
in the coordinate plane. From any point 
the knight moves to either 
or 
. Find the number of ways the knight can reach the point 
.
Solution
Let 
denote a move of 
units north and 
unit east, and let 
denote a move of unit north and units east. To get to the point using only these moves, say 
moves in direction and 
moves in direction , we must have 
because both the and -coordinates have increased by 
since the knight started. Solving this system of equations gives us 
. This means we need the knight to make 
moves, 
of which are headed in direction , and the remaining are headed in direction . Any combination of these moves work, so the answer is 
| 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 | ||
