-1

The Manhattan Distance between two points (a, b) and (c, d) is given by |a−c|+|b−d|, where |u−v| refers to the absolute value of (u−v).

Given an integer S, your task is to find the number of points (x, y), where both x and y are integers, such that the Manhattan Distance between (x, y) and (0,0) is at most S.

For example, suppose S= 1. The only point whose Manhattan Distance from (0,0) is exactly 0 is (0,0). The set of points whose Manhattan Distance from (0,0) is exactly 1 is {1,0),(0,1),(−1,0),(0,−1)}. Thus, there are 5 points whose Manhattan Distance from (0,0) is at most 1, and so the answer for S= 1 is 5.

Find the number of points whose Manhattan Distance from (0,0) is at most S for the following values of S:

(a) S= 4, (b) S= 10, (c) S= 23

Patrick Schick
  • 441
  • 3
    What did you try? Hint: how many positive integer solutions does the equation a+b = S have? – Tom Ariel Oct 14 '20 at 06:49
  • 1
    Welcome to MSE. You should choose your tags carefully. What has this to do with logic? Or with problem-solving? – José Carlos Santos Oct 14 '20 at 06:52
  • okay so I figured out the hint you gave at first glance, calculated three possible combinations. For example if x=y, or if any of them would be zero, and the others. But I could only come up with a brute force solution. Meaning, if the value of S would be something large (greater than 3 digits) I would not be able to solve it. – Patrick Schick Oct 14 '20 at 06:53
  • @JoséCarlosSantos, I found this question in a contest marked as Logical-Reasoning and Problem-Solving – Patrick Schick Oct 14 '20 at 06:54
  • 1
    Nevertheless, it is neither a question about Logic nor about problem-solving strategies. – José Carlos Santos Oct 14 '20 at 07:08

2 Answers2

1

Let us find all possible solution for $|x-0|+|y-0|=S$

There are $4$ obvious points $(S,0),(0,S),(-S,0),(0,-S)$.

The other points can be found as follows:Find all possible positive integer solutions to $x+y=S$. For any solution $(x,y)$ to the above equation, the $4$ points $(-x,-y),(-x,y),(x,-y),(x,y)$ lie at a Manhattan distance of $S$ from $(0,0)$.

Now number of positive integral solutions to $x+y=S$ is $S-1$ (namely $(1,S-1),(2,S-2),(3,S-3),\cdots,(S-1,1)$). Thus in total we get $4(S-1)+4=4S$ points.

Thus we get that the number of integral points at an exact Manhattan distance of $S$ from $(0,0)$ is $4S$

Hence the number of integral points at a Manhattan distance $\le S$ from $(0,0)$ is $4S+4(S-1)+\cdots+4+1$, where the last term, $1$, is due to the point $(0,0)$.

QED
  • 12,644
1

$$|x|+|y|\le s$$ can only have solutions for $|y|\le s$, or $y\in[-s,s]$. Then for a given $y$, $x\in[|y|-s,s-|y|]$, and there are $2(s-|y|)+1$ such numbers.

Then

$$\sum_{y=-s}^s(2(s-|y|)+1)=s^2+(s+1)^2.$$