The session was with about 10 students from 6th to 8th standard who were good in math, and it went for an hour. I have also highlighted a few ways of addressing wrong answers from curious students, along with a few comments which I feel could be helpful for teachers who read this. Names of the children have been changed for their privacy. I thank Prof. Kavita Sutar for her support and encouragement.
Question:
In this \(5 \times 7\) boxes grid, what is the smallest number of steps in which you reach END from S? You can move one box up, down, left, right, but not diagonally.
Me: Good. Can I reach in \(9\) steps?
Aarav: No! If you go right \(6\) steps and then go up \(4\) steps you will reach END, but you need \(10\) steps.
Me: Yes, but that’s not what I am asking for. Do you think I can reach END in \(9\) steps?
Aarav: I don’t know. Maybe you can’t.
Ananya: No, wait, even if you go Up Right Up Right Up Right Up Right then \(2\) Right, you need \(10\) steps. But that also does not mean that you can’t do it in \(9\) steps.
Me: Yes. You need to say, no matter how I travel, I can’t reach END in \(9\) steps.
Rohan: You can’t do that because END is \(4\) squares above and \(6\) squares right to START. So you must need at least \(4\) up and \(6\) right steps.
Me: Did everyone get what Rohan claims?
Aarav: Yeah. You can’t do in \(9\) steps.
Me: Okay. How many paths to END are there of length \(10\)? What do I mean by length \(10\), here?
Aarav: \(10\) steps.
Me: Yes, length of the path means number of steps in that path.
Aarav: There are \(35\) paths.
Me: Why? Whenever you shout out some number you need to say how you come up with that number and why that works? So why you say \(35\)?
Aarav: I guessed \(7 \times 5 = 35\).
Me: Okay. Let me ask this: How many paths are there? Is it \(6\)?
Aarav: You can mirror path along the diagonal.
Me: This is a very interesting observation. But again, are we in a square grid? What will mirroring of a path with Up Right Up Right Up Right Up Right look like?
After a minute of silence, maybe it's a good time to ask a relevant question to bring them back into the conversation. We can use some ideas discussed in earlier sessions for this. Here's one example:
Aarav: Oh that’s just \(6\). Because there are \(3\) ways to reach B and for each of these \(3\) ways there are \(2\) ways from B to C so it’s \(3 \times 2 = 6\).
Me: Suppose your friend disagrees with you and you want to prove him that you are correct? What do you do?
Diya: I will list all paths. For example there is a path \(a_1b_1\), \(a_1b_2\), \(a_2b_1\) and so on.
Me: Good. If suppose we want to list all paths, how shall we do it in our situation?
Aditya: There are too many paths.
Me: Never mind, let us write the paths on the board (see).
Aditya: I can give a direction sequence {U R U R R U R U R R R} where {U} means Up and {R} means Right.
Students already came up with clear notation. I remember one of my Professors, Lars Hellström, stressing that the effectiveness of having a good notation is key to solving half of the problem. See how Isha spots it below.
Rohan: Answer is \(210!\) (He came up with a very clever idea and it took a time to arrive at his solution.) He says there is \(1\) way to reach box marked \(A\) and \(1\) way to reach box marked \(B\). For the box marked \(C\), there are \(2\) ways because he has to reach \(C\) either via \(B\) or \(A\). Similarly, if you do it for every square you will get \(210\) for END.
Me: How do we proceed in general? Say there are \(x\) ways to reach box marked X and \(y\) ways to reach box marked Y.
Rohan: Then there are \(x+y\) ways to reach Box \(Z\).
This is a time that we make sure that everyone gets this idea clear and patch it up with the idea from last time.
Me: This is wonderful. What Rohan is saying is: if you have \(x\) ways to enter from one side of the room and if you have \(y\) ways to enter from the other side of the room, in total you have \(x+y\) ways to enter the room. Of course you can’t simultaneously enter from both sides; from the logic from the earlier class, it is disjoint union of possibilities or it follows logic “OR”, so we add things up!
Although Rohan’s answer is correct, the rest of the class is thinking about listing all the paths or coming up with a nice way of counting them without listing. It is our decision to pause Rohan’s idea for a while and then come back to it once we are done with the current line of thought. Here lies a challenging part. Since Rohan has already found the answer, we also need to decide whether he should learn another method. Of course, one need not be forced to learn every other way or to follow only the method that the rest of the class is using. In this case, I wanted him to learn the other trick, but I also felt that I must justify it to him correctly.
Me: Let us come back to listing our paths. How do we write all our paths?
Aarav: It is just a sequence of \(6\) Rs and \(4\) Us.
Me: Yes. But how many are there?
Aarav: \(2^{10}\) because at each place I can write either U or R.
Me: Can you go \(10\) Ups?
Aarav: \(5040\) because there are \(10\) ways to put the first U, \(9\) ways to put the second U, and \(8\) ways for third and \(7\) ways for fourth, so it is \(10 \times 9 \times 8 \times 7\).
Me: Are you sure that you are not overcounting? Are all Us distinct?
Isha: It is now just selecting \(4\) positions to place U, so it is \(\binom {10}{4}\).
Me: Great! Let us understand what Isha claims. Each path is a sequence of \(10\) length and you must place \(4\) U in that. And she is selecting positions to place U. But what goes wrong in Aarav’s idea?
After a few arguments, and with some children explaining to others what is going on
Aarav: Since all U are identical, we need to divide by \(4!\) so it is the same answer.
Me: Okay. Now we have \(3\) ways of arriving at the answer \(210\). Aarav and Isha’s idea seems to be the same. But what about Rohan’s idea, is it better? What if we need to compute the number of paths from start to end in a \(100\times 1000\) grid? Shall we proceed with Rohan’s idea?
Aditya: No, it is time-consuming.
Rohan: If the rectangle is small, my method is good. So it depends on the size of the boxes.
See, now he is understanding the point. Nevertheless, his idea has its own beauty. Arriving at that was certainly not our original motivation for the session. Math circle sessions very often go in unplanned, surprising, yet very beautiful directions.
Me: Let us go over Rohan’s idea once again. This time by filling in number of paths to each boxes from the start.
Akash: Diagonals look like a Pascal triangle!
After few curious, interesting observations and interaction among children, it is time to wrap up.
Me: You can inscribe this rectangle in Pascal triangle, see below.
Even though Rohan’s method is time-consuming for large squares, it is beautiful. Of course, there is another
way of inscribing the rectangle. Can you spot it?
We had a nice time. Some may feel that students are not precise about whether the path is the shortest, or that the language they used could have been better. That’s okay. As long as they are thinking correctly, we can always refine the rest. This problem is one such example of a low floor, high ceiling problem. After doing this session, one can emphasise Rohan’s recursive computation idea or take other variations of such problems — for example, introducing Catalan numbers to them. In fact, by the end of the discussion a few students were able to deduce the length of the shortest path from the bottom-left corner to the top-right corner, as well as a general formula for the number of such paths in an \(m \times n\) grid of boxes. A few also computed the number of paths that avoid the black square. Can you find answers for these?
Comments
Post a Comment