A person moves in the $x-y$ plane moving along points with integer co-ordinates $x$ and $y$ only. When she is at a point $(x,y)$, she takes a step based on the following rules: (a) if $x+y$ is even she moves to either $(x+1,y)$ or $(x+1,y+1)$; (b) if $x+y$ is odd she moves to either $(x,y+1)$ or $(x+1,y+1)$. How many distinct paths can she take to go from $(0,0)$ to $(8,8)$ given that she took exactly three steps to the right $((x,y)$ to $(x+1,y))$?
Problem
Source: Mumbai Region RMO 2014 Problem 4
Tags: analytic geometry, combinatorics unsolved, combinatorics
07.12.2014 14:06
Since she takes $3$ steps to the right and her final $x$-coordinate is $8$, therefore, she must have taken exactly $5$ diagonal steps. This means that she takes $3$ steps up. Furthermore, she can choose a diagonal step from any point on the plane. Now, note that, choosing the $5$ instances when she takes a diagonal step actually determines the path she takes. This is because, at any instant when she doesn't take the diagonal step, she has only one choice (right or up depending on $x+y$). Therefore, the number of paths is $\binom{5+3+3}{5} = \binom{11}{5}$.
07.12.2014 18:36
dibyo_99 wrote: This is because, at any instant when she doesn't take the diagonal step, she has only one choice (right or up depending on $x+y$). But surely you need an argument that all of these paths actually do end up at (8, 8)!
09.12.2014 10:55
If she takes $3$ steps right, $3$ steps up, and $5$ steps diagonally, she would quite obviously end up at $(8,8)$, right ?
09.12.2014 17:01
You have not shown that the 11-step path with diagonal steps as the 2nd, 3rd, 5th, 8th and 10th steps includes 3 steps up and 3 steps right.
09.12.2014 18:52
What you've written is correct @dibyo_99.
09.12.2014 19:13
I think (11,5) takes care of all the possibilities
09.12.2014 19:32
JBL wrote: dibyo_99 wrote: This is because, at any instant when she doesn't take the diagonal step, she has only one choice (right or up depending on $x+y$). But surely you need an argument that all of these paths actually do end up at (8, 8)! dibyo_99 wrote: If she takes $3$ steps right, $3$ steps up, and $5$ steps diagonally, she would quite obviously end up at $(8,8)$, right ? The argument given by dibyo_99 is quite correct. Since the person is allowed to go only $3$ steps to the right, she can go only $3$ units on the $x$-axis. And since she needs to reach $8$ on the $x$ axis, she must take exactly $5$ steps to reach the required point. But now having only options as going upwards and moving diagonally, she needs exactly $5$ diagonals as that is the only other step which can take her $+1$ unit on both axes. But moving right doesn't contibute to moving upwards. And since the $5$ diagonal steps contribute only $5$ steps upwards, she must take exactly $3$ steps upwards. Now fixing the diagonal steps will complementarily fix the steps upwards and towards the right or vice versa. So, the required answer is $\binom{11}{6}=\binom{11}{5}$.
09.12.2014 22:12
dibyo has correctly proved that every such sequence must consist of three up-steps, three right-steps and five diagonal steps. dibyo has correctly claimed that a path satisfying the given rules is determined by the number of steps and which ones are diagonal steps. But dibyo has not proved that an arbitrary choice of diagonal steps necessarily yields a path with 3 up and 3 right steps. (This is not difficult, but it is necessary to complete the proof.)
10.12.2014 08:11
YESMAths wrote: JBL wrote: dibyo_99 wrote: This is because, at any instant when she doesn't take the diagonal step, she has only one choice (right or up depending on $x+y$). But surely you need an argument that all of these paths actually do end up at (8, 8)! dibyo_99 wrote: If she takes $3$ steps right, $3$ steps up, and $5$ steps diagonally, she would quite obviously end up at $(8,8)$, right ? The argument given by dibyo_99 is quite correct. Since the person is allowed to go only $3$ steps to the right, she can go only $3$ units on the $x$-axis. And since she needs to reach $8$ on the $x$ axis, she must take exactly $5$ steps to reach the required point. But now having only options as going upwards and moving diagonally, she needs exactly $5$ diagonals as that is the only other step which can take her $+1$ unit on both axes. But moving right doesn't contibute to moving upwards. And since the $5$ diagonal steps contribute only $5$ steps upwards, she must take exactly $3$ steps upwards. Now fixing the diagonal steps will complementarily fix the steps upwards and towards the right or vice versa. So, the required answer is $\binom{11}{6}=\binom{11}{5}$. nicely explained !
11.12.2014 14:39
I think answer is as follows 5 diagonal steps,3 right steps and 3 up steps can be done in following ways $ \frac{11!}{3!3!5!} $
11.12.2014 17:15
Incorrect; right and up steps cannot be done at will. You can only move diagonally or not diagonally. For example, at the beginning, you cannot move up, only diagonally or not diagonally (to the right).
11.12.2014 17:55
Levinay wrote: I think answer is as follows 5 diagonal steps,3 right steps and 3 up steps can be done in following ways $ \frac{11!}{3!3!5!} $ Yeah, to avoid this confusion, we also need to prove that fixing the diagonal steps will automatically fix (or better- will adjust) the right and up steps according to the parity of $x+y$. Or we can prove the other way round- right and up steps fix the diagonals, which seems more vague to begin proving than the previous case. That is what JBL wanted to say.
11.12.2014 19:40
YESMAths wrote: Levinay wrote: I think answer is as follows 5 diagonal steps,3 right steps and 3 up steps can be done in following ways $ \frac{11!}{3!3!5!} $ Yeah, to avoid this confusion, we also need to prove that fixing the diagonal steps will automatically fix (or better- will adjust) the right and up steps according to the parity of $x+y$. Or we can prove the other way round- right and up steps fix the diagonals, which seems more vague to begin proving than the previous case. That is what JBL wanted to say. thats great....liked that word "parity" thanks both
11.12.2014 21:52
i got 357 by counting as it would be sigma x*y*z such that x+y+z<=6 where x,y,z are non negative integers and if x*y*z is zero then if anyone of them(x,y,z) is 0, considered it as 1 in x*y*z that is if x=0 then y*z to be considered..
12.12.2014 01:43
And what is supposed to be the connection between this calculation and the problem?
12.12.2014 12:01
oops i made an error in understanding. it should be SUM{(x+1)*(y+1)*(z+1)} such that x+y+z<=5, which is simply coefficient of x^8 in (x/(1-x)^2)^3*(1-x)^-1 which is 11C5. Calculation and logic is indirect long so i omit it.