0
$\begingroup$

Suppose we are on a finite 2D grid of points from $(-a,-b)$ to $(a,b)$. In the beginning, we are at the point $(0,0)$ inside the grid. How many points are there that have distance $k$ between $(0,0)$?

$\endgroup$
0
$\begingroup$

Are you asking how many vertices have distance exactly $k$ from $(0,0)$?

If so, the answer is $4k$ for any $k$ which is at least one, and less than or equal to $\min\{a,b\}$.

You can check this inductively.

Look at how the vertices at distance 2 in the grid branch out from those at distance 1. The three red vertices in quadrant 1 ($x \geq 0$ and $y \geq 0$) are all adjacent to the two blue vertices in quadrant 1. A similar pattern holds in all four quadrants.

enter image description here

So let our inductive hypothesis be that the number of vertices at distance $k$ from (0,0) in any single quadrant is $k+1$. (This is true for $k=1$, so we have a base case).

Now let's prove it for distance $k+1$. Let's first assume we are in the first quadrant. Each vertex at distance $k$ (of which there are k+1 by assumption) has exactly 1 neighbour, directly above it, at distance $k+1$. But, there is also one extra neighbour. The vertex at distance $k$ on the x-axis has a neighbour at distance $k+1$ directly to the right (see the figure below, the 'extra' neighbour to the right has a little + next to it). Thus in quadrant 1, there are $k+2$ vertices at distance $k+1$ from (0,0).

This proof works for the other quadrants by 'rotating' the argument, as shown in the figure below. This completes the proof by induction that each quadrant contains $k+1$ vertices at distance $k$ from $(0,0)$.

Note that the vertices on the axes get double-counted, as they lie in two quadrants. We know each quadrant has $k+1$ vertices at distance $k$, and there are 4 quadrants, with 4 vertices double-counted, so the total number of vertices at distance $k$ is $4(k+1) - 4 = 4k$.

enter image description here

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. But I want to know when we are on the finite grid, like when we're in the middle of the grid graph $P_n \box P_m$. Do we have any ways to find how many points that have distance $k$ from where we are? $\endgroup$ – Nuttanon Apr 28 '20 at 9:46
  • $\begingroup$ Because of symmetry (everywhere on the inside of the grid looks the same), this answer works anywhere on the grid, except if you are distance less than $k$ from one of the boundaries. If you are near the boundaries, that's a lot messier =/ $\endgroup$ – Brandon du Preez Apr 28 '20 at 13:47
  • $\begingroup$ I just wondering that is there any function that will depend on 3 variables n, m, and k to find the total number of vertices at distance $k$. $\endgroup$ – Nuttanon Apr 28 '20 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.