Minimum number of unique angles

Probability Level 4

For each pair of integers $1 \leq x \leq 5, 1 \leq y \leq 5$ , draw a line connecting $(0,0)$ to $(x,y)$ .

How many distinct lines do we obtain?

BONUS: Generalize for $1 \le x\le X$ and $1 \le y\le Y.$

The answer is 19.

1 solution

Phillip Smith
Nov 13, 2017

The angle, or more simply, the gradient, can be expressed as $\dfrac { x }{ y }$ .

Two lines are equal if they are formed from the points $(i, j), (i', j')$ where $\dfrac{i'}{j'} = \dfrac{i}{j}$ . For example, the points $(2,4) , (1,2)$ give us the same line \( y = 2x ).

Thus, to count the number of unique lines, we can simply find the cases where $ \gcd (i, j) = 1 $.

When $x = 1$ , there are 5 values of $y$ where $\gcd (i,j) = 1$ .
When $x = 2$ , there are 3 values of $y$ where $\gcd (i,j) = 1$ .
When $x = 3$ , there are 4 values of $y$ where $\gcd (i,j) = 1$ .
When $x = 5$ , there are 3 values of $y$ where $\gcd (i,j) = 1$ .
When $x = 5$ , there are 4 values of $y$ where $\gcd (i,j) = 1$ .

Thus, there are a total of 19 lines.

I think you meant $[0,5]$ instead of $(0,5)$ for your interval.

Patrick Corn - 3 years, 6 months ago

Hmm, maybe? Can you explain for me why it would be one over the other?

Phillip Smith - 3 years, 6 months ago

It looks like you fixed it, but the answer seems to include values with $x=5$ or $y=5.$

Patrick Corn - 3 years, 6 months ago

@Patrick Corn – It should be for all combinations of $0\le x\le 5$ and $0\le y\le 5$

This means there should be 36 combinations $(0,0), (0,1), ..., (1,0), (1,1), ..., (5,4), (5, 5)$

Edit: I realised what you meant. I thought $x\in (a,b)$ included $a$ and $b$ . I was wrong. Thanks for the pick-up!! I was thinking of $x\in [a,b]$ . I find it hard to remember which is which, sometimes.

Phillip Smith - 3 years, 6 months ago

This is incorrect, because it doesn't count $(0,0)$ while the problem explicitly states that it's counted.

Ivan Koswara - 3 years, 6 months ago

I believe it does. $GCD(0,0)=0$ (from wolfram alpha)

$\therefore \left| sgn(GCD(0,0)-1) \right|=1$

Which adds to the number of unique angles

Phillip Smith - 3 years, 6 months ago

In fact, your final formula doesn't even agree with the answer you put in. $\text{sgn}(|\gcd(x,y) - 1|)$ is 1 for these pairs: $(0,0), (0,2), (0,3), (0,4), (0,5), (2,0), (2,2), (2,4), (3,0), (3,3), (4,0), (4,2), (4,4), (5,0), (5,5)$ . There are 15 such pairs, so your formula would give $27 - 15 = 12$ . Note that you're subtracting the pairs that have $\text{sgn}(|\gcd(x,y) - 1|) = 1$ , not adding them.

The number 27 is incorrect; the correct number is $(X+1)(Y+1) + 1 = 37$ . All possible pairs $(x,y)$ are counted, and you subtract those with GCD not 1 from the summation; after that, you add 1 more for $(0,0)$ because otherwise it would be subtracted.

Ivan Koswara - 3 years, 6 months ago

@Ivan Koswara – Hmm... So how would the formula be corrected?

Phillip Smith - 3 years, 6 months ago

@Phillip Smith – $\displaystyle 1 + \sum_{x=0}^X \sum_{y=0}^Y \mathbf{1}_{\{\gcd(x,y) = 1\}}(x,y)$ , where $\mathbf{1}_A$ is the characteristic function on $A$ . Basically all pairs with GCD 1, plus the $(0,0)$ pair. Using $\text{sgn}(|\gcd(x,y) - 1|)$ is very unclear.

Ivan Koswara - 3 years, 6 months ago

Minor typo: $1\le x\le 5$ was typed twice.

Micah Wood - 3 years, 3 months ago

Minimum number of unique angles

The answer is 19.

1 solution

0 pending reports