Mathematical Circles - on TV!
After a long, long time, a bunch of students got together at my place yesterday to participate in an online programming contest - http://opc.kurukshetra.org.in/opc/! They didn't win any prizes, but at least, they had the enthusiasm to *try* ... If you check out some of the prize winners - you will notice something interesting - many of them are Russians! But then, you will find a large number of these guys winning prizes in the world's most prestigious coding contest - the ACM ICPC - more interesting, it seems that many of them don't have a CS background - but do stuff like Math and Physics! I am currently reading a book called Mathematical circles which, as the authors say, was originally written to help people in the former Soviet Union who dealt with extracurricular math education. The old comrades have converted math into some kind of competitive sport (like Chess, in which too they excelled). Kids (as young as 10 years) are taught how to do math the *proper* way, rather than memorizing (a+b)**2 = a**2 + b**2 + 2ab ... and it makes *very* interesting reading. The second chapter is on `parity' - and it simply says - an even number is said to have even parity and an odd number, odd parity. Simple, isn't it. The authors go on to demonstrate some elementary problems and how an awareness of parity becomes central to their solution. Here is a sample:
- On a chessboard, a knight starts from square a1 and returns there after making several moves. Show that the knight makes an even number of moves
- A closed path is made up of 11 line segments. Can one line, not containing a vertex of the path, intersect each of its segments?
Mathematics Education Blog » Blog Archive » Mathematical Circles - on TV!
Mon Jan 21 17:10:26 2008
[...] Henry Cate: [...]
Tue Jan 22 00:36:18 2008
Sir, I sent you the solutions in email as there is no screening here. Anyway the Knight problem, I think I had heard something similar earlier eventhough not exactly the same one. For the second one, it looked really simple and it is that argument which I sent you. Haven't done in-depth proof or anything. I hope, that they are correct! - Sandeep. PS: If my proofs are indeed correct, then I should say that the problems were easy ... otherwise... they were too difficult :)
Tue Jan 22 00:49:50 2008
Sandeep, The solutions are correct!
Wed Jan 23 16:16:46 2008
I believe, the basic idea used to prove the knight problem is that, a single move of a knight is either 2h + 1v, or, 2v + 1h (where `h' stands for horizontal, and `v' for vertical). If the knight has moved x squares horizontally, and y squares vertically, then to be back to the same position, this x should be even, and so should y (unless the knight is killed, and re-incarnated :)). Therefore, if n steps were taken, then the knight would have moved n_1(2h + 1v) + n_2(1h + 2v) steps, where n=n_1+n_2. Now, to reach back to the initial position, 2n_1+n_2 should be even, and so should n_1+2n_2 ==> n_1 and n_2 should be even ==> n should be even. That was probably not a well-written proof :) .. and the next one, is just a contradiction by example. I do not know if I understood the problem clearly, though. I drew a graph of ten nodes and ten links, five nodes on each sides, with 9 links arranged in a zig-zag manner, and the final link connecting 2 corner nodes (that would otherwise have degree one) diagonally (well, its like re-arranging nodes of a circle with even number of nodes, in a straight line, and pulling every other node laterally in a direction). The eleventh line segment forms the intersecting line segment.
Wed Jan 23 19:02:56 2008
Sir, is it time to publish the results? I asked these problems to my students today! (may be I am a bad teacher, as they couldn't solve) - Sandeep.
Wed Jan 23 19:12:23 2008
@Dinil Your first proof looks good. You definitely can include the points which I am to tell now. But they are missing as of now. There can be moves like -2h+1v or 2h-1v or 1h-2v or -1h+2v .. (basically all the vectors you can create with h and v and coefficients plus/minus 2 and 1 - but never two ones / two twos together -- gives 8 of them). Your proof has to include them too. And I appreciate you very much, as I started the way you started and found it really hard. Then I followed "Feynman" principle - Read the problem, Think well, then solve (I made use of the clue hidden in sir's blog) Your proof for second one is not a complete proof. HINT: "PARITY". Sandeep.
Thu Jan 24 06:01:34 2008
Sandeep, Yes - you can put up the solutions!
Thu Jan 24 06:37:02 2008
@ Sandeep, The sign was there in the mind; but it appeared trivial. I should have mentioned it though; thanks. Yes, the second one, is not a proof. If it is to disprove by example, it could be scientific (but not for proving).
Thu Jan 24 09:14:42 2008
1. Every jump changes color. Coming back to the same color takes even number of jumps. The initial position is the final position means both are of same color and hence there must have been even number of jumps in between. 2. If indeed there is such a line, it would cut all the 11 segments, by putting half of the vertices on one side and other half on the other side of the line. Here there are 11 vertices – which means, that one side will have more than half. Not possible! (valid for any odd integer)
Thu Jan 24 09:30:41 2008
Sir, where did you buy this book (Mathematical circles) from? I am interested in grabbing one copy.
Fri Jan 25 06:10:56 2008
I got it from Cosmo books - they distribute Universities Press titles. http://www.universitiespress.com/
Fri Jan 25 13:43:17 2008
Oh .. at Cosmo books - that is good. I got a copy from our library. Strange, it was last issued in 1997 .. and now, its the second time someone is borrowing it! .. and yes, its an interesting book. Very informative post, Sir. Thanks a lot.
Tue Jan 29 03:15:11 2008
There is this prof in our CS dept, Dr Brian Dean a MIT alumnus who takes this programming and problem solving seminar course. Its pretty interesting and incidentally last week he was speaking about parity. This is the nice question he had asked all of us to solve. Bessie and Clara (two cows, of course) are playing paintball in an M x N yard. Bessie starts at (bx, by) and Clara starts at (cx, cy) They take turns moving, with Bessie moving first. Each move, a cow must travel one step in a single direction: up, left,down, or right. However, if this process carries the cow through the same x or y coordinate of the other cow, it loses (since the cows can only shoot along vertical or horizontal lines, (obviously). Cows can assume any integer-valued position in the yard from (0,0) up to (M, N). Given M and N (two integers ? 1000) and integers (cx, cy) as input, count the number of starting positions (bx, by) for Bessie (excluding those where bx=cx or by=cy) for which Bessie can guarantee that she will win the game. You can do it with programming or also one can more or less formulate an equation for any MxN field.
Tue Jan 29 03:39:15 2008
There is a short and sweet slides on parity, any one needs let me know.