1

Question: Let $n$ be a positive integer. Consider a square $S$ of side $2n$ units with sides parallel to the coordinate axes. Divide $S$ into $4n^2$ unit squares by drawing $2n−1$ horizontal and $2n−1$ vertical lines one unit apart. A circle of diameter $2n−1$ is drawn with its centre at the intersection of the two diagonals of the square $S$. How many of these unit squares contain a portion of the circumference of the circle? Source

My answer:

It's obvious that we are basically talking about the incircle of the square. So as it's four quarters are symmetrical, if we find the number of squares lying on the circumference of just one quarter, multiplying it with four must give us our desired result.

Considering any one quarter, we observe that the circle touches the side of the square at the mid-point, so number of squares touching the circumference will be equal to the number of columns falling in half of the square, which is $4 (\frac{2n-1}2)= 4n-2$.

I find my solution doubtful; Am I correct?

Any alternate solutions will be much appreciated.

tryst with freedom
  • 11,538
Stranger Forever
  • 1,313

2 Answers2

2

For example, here is the case $n=10$, with squares containing a piece of circumference highlighted.

enter image description here

Notice that some columns contain one highlighted square in the first quadrant, others two, three or four.

But note that each highlighted square in the first quadrant is obtained from the previous one by moving either one unit right or one unit down. And the total number of steps is ...

Robert Israel
  • 448,999
  • In your case, it is 76.. but how do I generalize the result.. I cannot draw this in an exam hall.. how do I tackle then? – Stranger Forever Jun 02 '20 at 01:41
  • How many vertical steps and how many horizontal steps must there be, for any $n$? – Robert Israel Jun 02 '20 at 15:16
  • In one quadrant? – Stranger Forever Jun 02 '20 at 19:12
  • If you can do it for one quadrant, you can do it for the whole thing. – Robert Israel Jun 02 '20 at 19:45
  • Considering the first quadrant, as there are $10$ columns, and for each, we are either going one unit right or down (as you said) so there will be a total of $(10.2-1)$ possibilities.. so is that it? If so, how am I going to know this without drawing the figure? And will it be true for all $n$? How do I show that? – Stranger Forever Jun 03 '20 at 03:59
  • The logic is the same for all $n$. – Robert Israel Jun 03 '20 at 13:33
  • @RobertIsrael: In the hopes of getting Buraian to see the pure simplicity and logic in your answer, I added another "answer" in an attempt to explain why and how yours is the correct one. If you feel like explaining it yourself, feel like mine mischaracterises yours, or you plain don't like mine for whatever reason, let me know: I just thought that maybe someone else butting in would help here. – Glärbo Jun 11 '21 at 09:54
1

I applaud Robert Israel's answer and approach: this is how answers should be written.

Unfortunately, the asker seems to find it "unconvincing". Consider this an extended comment, explaining exactly why Robert Israel's answer is correct, and why the approach he guided to yields a robust, intuitive reason why it is correct.

Because the square contains $2n \times 2n$ square cells, the diagonals intersect at an intersection of four cells. If we choose this point as the origin, then each horizontal and vertical line is at an integer coordinate; and each cell spans a square between consecutive integer coordinates.

The circle is then centered at origin with radius $n - \frac{1}{2}$, and all four quadrants around origin are symmetric, and the number of cells the circle intersects will be divisible by $4$ for all positive integer $n$.

If we consider the circular arc from the positive $x$ axis to the positive $y$ axis, we can trace the cells the circle intersects, one by one.

If the circle intersects the left edge of the cell, the next cell will be the cell on the left side.

If the circle intersects the top edge of the cell, the next cell will be the cell above.

Since we are traversing the arc from positive $x$ axis to the positive $y$ axis, the only other way the circle can intersect the cell perimeter is via the upper left corner, if and only if there are integers $u$, $v$ such that $$u^2 + v^2 = \left(n - \frac{1}{2}\right)^2$$ i.e. $$u^2 + v^2 = n^2 - n + \frac{1}{4}$$ For integer $n$, the right side is never an integer, so there cannot be such integers $u$ and $v$, and therefore the circle with radius $n + \frac{1}{2}$ (with positive integer $n$) never passes through any points with integer coordinates; so the "left" and "up" steps are the only two possible ones.

Because the arc must do $n-1$ steps up, and $n-1$ steps left, it must pass through exactly $$4 \bigl( 1 + (n - 1) + (n - 1) \bigr) = 8 n - 4$$ cells. (The $1$ is the starting cell, and the two $(n - 1)$ are the number of steps up and left; and since this is only one quadrant and all four are identical, we multiply by four.)

The way the walk is done just changes the order in which the "up" and "left" steps taken; it does not change the number of steps either way. This can sound funny, but is actually a common thing in similar calculations. In a very real sense, we are calculating here the Manhattan length or taxicab length of the circular arc. Indeed, walking from the starting cell to the final cell in the first quadrant will always take one through $2n - 1$ cells, regardless of whether one walks in a straight line, or along two edges of the $n \times n$ quadrant; the circular arc just happens to be somewhere in between.

Glärbo
  • 234
  • It's crazy how much depth of thinking is required to formalize this apparently simple question – tryst with freedom Jun 11 '21 at 08:40
  • @Buraian: Well, no, not really. You see, it is more a question of how you approach and understand the problem and the answer Robert Israel has provided. As I read his answer and suggestions, everything I wrote above occurred to me, basically in sequence. The only "original" part is the proof of why diagonal steps are not possible in the $n-1/2$-radius circle case. Everything else he showed or pointed at. Granted, I did know about Taxicab/Manhattan geometry from before, but still: I got the thrill of discovery and everything, all within a couple of minutes, based on his answer. – Glärbo Jun 11 '21 at 10:00
  • (If diagonal steps were possible, each diagonal step would reduce the total result by four cells. But, because that can only happen for a circle centered at origin when $u^2 + v^2 = r^2$ (plain old Pythagoras!), and $r = n - 1/2$ –– oops, need to fix that sign typo in the answer –– it cannot happen here, so no matter what positive integer $n$ is, the answer is always $8 n - 4$.) – Glärbo Jun 11 '21 at 10:03
  • Thank you for the answer, I will go over it a few times and comment – tryst with freedom Jun 11 '21 at 11:21
  • I think a bit more introductory discussion on the taxicab metric may also be nice in the answer – tryst with freedom Jun 11 '21 at 14:39
  • This is such a gemstone answer, thank you – tryst with freedom Jun 11 '21 at 23:02