MathDB

5

Part of 1989 Irish Math Olympiad

Problems(2)

Ireland Olympiad number theory

Source: IrMO 1989 Paper 1 Q.5

1/5/2016
Let x=a1a2…anx = a_1a_2 \dots a_n be an n-digit number, where a1,a2,…,an(a1≠0)a_1, a_2, \dots , an (a_1 \neq 0) are the digits. The nn numbers x1=x=a1a2...an, x_1 = x = a_1 a_2 ... a_n, x2=ana1...an−1, x_2 = a_n a_1 ... a_{n-1}, x3=an−1ana1...an−2 x_3 = a_{n-1} a_n a _1 ... a_{n-2} , x4=an−2an−1ana1,...an−3, x_4 = a_{n-2} a_{n-1} a_n a_1 , ... a_{n-3} , ...,xn=a2a3...ana1 ... , x_n = a_2 a_3 ... a_n a_1 are said to be obtained from xx by the cyclic permutation of digits. [For example, if n=5n = 5 and x=37001x = 37001, then the numbers are x1=37001,x2=13700,x_1 = 37001, x_2 = 13700, x3=01370(=1370),x4=00137(=137),x_3 = 01370(= 1370), x_4 = 00137(= 137), x5=70013.] x_5 = 70013.] Find, with proof, (i) the smallest natural number n for which there exists an n-digit number x such that the n numbers obtained from x by the cyclic permutation of digits are all divisible by 1989; and (ii) the smallest natural number x with this property.
Divisibilitynumber theory
Bertrand and Prime Counting

Source: IrMO 1989 Paper 2 Problem 5

9/29/2017
(i): Prove that if nn is a positive integer, then (2nn)=(2n)!(n!)2\binom{2n}{n}=\frac{(2n)!}{(n!)^2} is a positive integer that is divisible by all prime numbers pp with n<p≤2nn<p\le 2n, and that (2nn)<22n.\binom{2n}{n}<2^{2n}.
(ii): For xx a positive real number, let π(x)\pi(x) denote the number of prime numbers p≤xp \le x. [Thus, π(10)=4\pi(10) = 4 since there are 44 primes, viz., 22, 33, 55, and 77, not exceeding 1010.]Prove that if n≥3n \ge 3 is an integer, then (a)π(2n)<π(n)+2nlog⁡2(n);\pi(2n) < \pi(n) + {{2n}\over{\log_2(n)}};(b)π(2n)<2n+1log⁡2(n−1)n;\pi(2^n) < {{2^{n+1}\log_2(n-1)}\over{n}};(c) Deduce that, for all real numbers x≥8x \ge 8,π(x)<4xlog⁡2(log⁡2(x))log⁡2(x).\pi(x) < {{4x \log_2(\log_2(x))}\over{\log_2(x)}}.
number theory