Olympiad Maths Prep

Track / Stage 7 / 242 of 300 #1642 of 2000

Problem 1642

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.5 Find the answer

A lattice point (x,y,z)Z3(x, y, z) \in Z^3 can be seen from the origin if the line from the origin does not contain any other lattice point (x,y,z)(x', y', z') with (x)2+(y)2+(z)2<x2+y2+z2.(x')^2 + (y')^2 + (z')^2 < x^2 + y^2 + z^2. Let pp be the probability that a randomly selected point on the cubic lattice Z3Z^3 can be seen from the origin. Given that
1p=n=ikns\frac{1}{p}= \sum^{\infty}_{n=i} \frac{k}{n^s}
for some integers i,k i, k, and ss, find i,ki, k and ss.

Official solution

To solve this problem, we need to determine the probability p p that a randomly selected point (x,y,z)Z3(x, y, z) \in \mathbb{Z}^3 can be seen from the origin. A point (x,y,z)(x, y, z) can be seen from the origin if and only if the greatest common divisor (gcd) of xx, yy, and zz is 1, i.e., gcd(x,y,z)=1\gcd(x, y, z) = 1.

1. **Understanding the Probability p p **:
The probability p p that a randomly selected point (x,y,z)(x, y, z) can be seen from the origin is the probability that gcd(x,y,z)=1\gcd(x, y, z) = 1. This is equivalent to the probability that xx, yy, and zz are coprime.

2. Using the Principle of Inclusion-Exclusion:
To find this probability, we use the principle of inclusion-exclusion. For a prime p p , the probability that p p divides at least one of x x , y y , or z z is:
P(px or py or pz)=1P(px and py and pz) P(p \mid x \text{ or } p \mid y \text{ or } p \mid z) = 1 - P(p \nmid x \text{ and } p \nmid y \text{ and } p \nmid z)
Since x x , y y , and z z are independently chosen, the probability that p p does not divide any of them is:
P(px)=P(py)=P(pz)=11p P(p \nmid x) = P(p \nmid y) = P(p \nmid z) = 1 - \frac{1}{p}
Therefore,
P(px and py and pz)=(11p)3 P(p \nmid x \text{ and } p \nmid y \text{ and } p \nmid z) = \left(1 - \frac{1}{p}\right)^3
Hence,
P(px or py or pz)=1(11p)3 P(p \mid x \text{ or } p \mid y \text{ or } p \mid z) = 1 - \left(1 - \frac{1}{p}\right)^3

3. Complementary Probability:
The probability that x x , y y , and z z are coprime is the product over all primes p p of the complementary probabilities:
p=p prime(1P(px or py or pz))=p prime(1(1(11p)3)) p = \prod_{p \text{ prime}} \left(1 - P(p \mid x \text{ or } p \mid y \text{ or } p \mid z)\right) = \prod_{p \text{ prime}} \left(1 - \left(1 - \left(1 - \frac{1}{p}\right)^3\right)\right)
Simplifying the expression inside the product:
p=p prime(1(1(11p)3))=p prime(1(1(13p+3p21p3))) p = \prod_{p \text{ prime}} \left(1 - \left(1 - \left(1 - \frac{1}{p}\right)^3\right)\right) = \prod_{p \text{ prime}} \left(1 - \left(1 - \left(1 - \frac{3}{p} + \frac{3}{p^2} - \frac{1}{p^3}\right)\right)\right)
p=p prime((11p)3) p = \prod_{p \text{ prime}} \left(\left(1 - \frac{1}{p}\right)^3\right)

4. Using the Riemann Zeta Function:
The product over all primes can be expressed using the Riemann zeta function ζ(s)\zeta(s):
p prime(11ps)=1ζ(s) \prod_{p \text{ prime}} \left(1 - \frac{1}{p^s}\right) = \frac{1}{\zeta(s)}
Therefore,
p=p prime(11p)3=1ζ(3) p = \prod_{p \text{ prime}} \left(1 - \frac{1}{p}\right)^3 = \frac{1}{\zeta(3)}
Hence,
1p=ζ(3) \frac{1}{p} = \zeta(3)

5. **Identifying i i , k k , and s s **:
Given that 1p=n=ikns\frac{1}{p} = \sum_{n=i}^{\infty} \frac{k}{n^s}, we recognize that this is the definition of the Riemann zeta function ζ(s)\zeta(s) for s=3 s = 3 , starting from n=1 n = 1 with k=1 k = 1 :
ζ(3)=n=11n3 \zeta(3) = \sum_{n=1}^{\infty} \frac{1}{n^3}

The final answer is i=1 \boxed{ i = 1 } , k=1 k = 1 , and s=3 s = 3 .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.