MathDB
matrix of n rows, conditions hold

Source: France 1988 P1

May 18, 2021
matrixnumber theory

Problem Statement

Let us consider a matrix TT with n rows denoted 1,…,n1,\ldots,n and pp columns 1,…,p1,\ldots,p. Its entries aik (1≤i≤n,1≤k≤p)a_{ik}~(1\le i\le n,1\le k\le p) are integers such that 1≤aik≤N1\le a_{ik}\le N, where NN is a given natural number. Let EiE_i be the set of numbers that appear on the ii-th row. Answer question (a) or (b).
(a) Assume TT satisfies the following conditions: (1)(1) EiE_i has exactly pp elements for each ii, and (2)(2) all EiE_i's are mutually distinct. Let mm be the smallest value of NN that permits a construction of such an n×pn\times p table TT. i. Compute mm if n=p+1n=p+1. ii. Compute mm if n=1030n=10^{30} and p=1998p=1998. iii. Determine lim⁡n→∞mpn\lim_{n\to\infty}\frac{m^p}n, where pp is fixed.
(b) Assume TT satisfies the following conditions instead: (1)(1) p=np=n, (2)(2) whenever i,ki,k are integers with i+k≤ni+k\le n, the number aika_{ik} is not in the set Ei+kE_{i+k}. i. Prove that all EiE_i's are mutually distinct. ii. Prove that if n≥2qn\ge2^q for some integer q>0q>0, then N≥q+1N\ge q+1. iii. Let n=2r−1n=2^r-1 for some integer r>0r>0. Prove that N≥rN\ge r and show that there is such a table with N=rN=r.
Back to ProblemsView on AoPS