A lattice point is a point with integer coordinates such as (2,3). An object in the plane moves from one lattice point to another. At each step, the object may move one unit to the right, one unit to the left, one unit up, or one unit down. If the object starts at (0,0) and takes a 10-step path, how many different points could be the final point?
The object can get to any point in the square at (5,5), (5,-5), (-5,-5), (-5,5), so the answer is 100 poins.
+121 The answer is 286. It comes from the following sum:\(1+(1+2)+(1+2+3)+(1+2+3+4)+...+(1+2+3+...+11)=\)
1+3+6+10+15+21+28+35+45+55+66 = 286.
It is the number of ordered partitions of 10 as the sum of four numbers taken from the set \({{0, 1, 2, ..., 10}}\). If we write these partitions as 4-tuples such as (3, 2, 0, 5), and take the coordinates to mean, say,
(3 units to the right, 2 units up, no movement to the left, 5 units down), then each partition would be uniquely associated with a lattice point in the plain (or is that plane?!). I have carefully counted the number of such ordered partitions and have a list of them, but am too tired at the moment to list them. The sum can also be written as
\({2 \choose 0}+{3 \choose 1}+{4 \choose 2}+{5 \choose 3}+ {6 \choose4}+{7 \choose 5}+{8 \choose 6}+{9 \choose 7}+{10 \choose 8}+{11 \choose 9}+{12 \choose 10}\)
+121 Our guest is asolutely right; the number 286 is way too large. The problem is that the statement I made, that "each partition would be uniquely associated with a lattice point", is not correct since there are duplications. For instance, (0, 4, 1, 5) and (2, 2, 3, 3) both take you to the terminal point (-1, -1) on the plane. I am trying to figure out how many duplications there are among the 286 partitions so that I can subtract thatnumber from the total.
Also geometrically, an approach that the first answer hinted at, the terminal points, I think, may lie on the following lattice :
If so , the number of terminal points would be \(2(1+3+5+...+19) +21=2(100)+21=221\). That would mean that among the 286 partitions I counted there were 65 duplications.
+121 The lattice I have given is precisely the set of points we are looking for. But a proof is wanting.
(Notice that 'our friend with the few words of encouragement' who said to my partitions "bits iss wrong" has packed his bags and left the ring. That to me is an indication that he/she has either run out of words completely or that I have happened to hit the jackpot with my poorly dotted diagram of the terminal points. Have we been mean to him/her, perhaps? Is it possible that English is his/her third or fourth tongue, and that that tongue is still developing? I remember a long time ago as an exchange student I developed an intense dislike for anyone who expected me to talk with more words than the vocabulary of a parrot contains. In fact for about 6 months after arrival I hardly opened my mouth. I guess I was waiting for the moment of glory, when my English would suddenly become bedazzlingly fluent and my voice commanding and irresistable. Of course that never happened, but I manage and yet still have very little to say.)
I am still looking for the overlapping partitions though even though I am becoming convinced that that approach is suffering from a fundamental flaw; there are too many overlaps and not enough partitions to cover all 221Points.
