الرياضيات
نظرية الأعداد

Combinatorial number theory

1. Overview

Unlike in a previous lecture where we discussed various number theory theorems like LTE\mathrm{LTE} and Chinese Remainder Theorem, here we look into combinatorial problems with a strong number theory flavour. That is why this lecture will not be theorem based but rather filled with interesting problems that are useful examples.

2. Problems

    1. Let nn be a 2525 digit number without a single 99 as its digit. Prove that it is possible to pick two of its digit, add one to them and obtain a number not divisible by 77.
    1. Let MM be a set of natural numbers with 20252025 elements such that none of elements of MM has a prime divisor bigger than 2626. Prove that it is possible to pick four distinct elements of MM: x1,x2,x3,x4x_1, x_2, x_3, x_4 such that x1x2x3x4=t4x_1 x_2 x_3 x_4 = t^4 for some integer tt.
    1. Assume that MM is a subset of {1,2,,15}\{1, 2, \dots, 15\} such that the product of any three distinct elements of MM is not a square. What is the maximal possible cardinality of MM?
    1. What is the maximal number of elements of {105,106,,210}\{105, 106, \dots, 210\} that can be picked such that each pair of them is coprime?
    1. Let 0<a1<a2<<a101<50500 < a_1 < a_2 < \dots < a_{101} < 5050 be integers. Prove that there exist different integers ai,aj,ak,ala_i, a_j, a_k, a_l with 5050ai+ajakal5050 \mid a_i + a_j - a_k - a_l.
    1. Is it possible to arrange numbers from 11 to 20132013 around circle such that for each two neighbours x,yx, y we have 503xy1005503 \le |x - y| \le 1005?
    1. Let pp be a prime and let kpk \le p. Let A={a1,a2,,a2k1}A = \{a_1, a_2, \dots, a_{2k-1}\} such that no kk among them give the same residue modulo pp. Prove that if considered sums modulo pp of subsets of size kk of set AA - there must appear at least kk distinct sums.
    1. If pp is a prime number, prove that among 2p12p-1 integers there must be at least pp integers with sum divisible by pp.
    1. (Erdos-Ginzburg-Ziv theorem) For every positive integer nn, prove that among 2n12n-1 integers there exist nn integers whose sum is divisible with nn.
    1. Is there an n>1n > 1 such that it is possible to construct disjoint sets A1,A2,,AnA_1, A_2, \dots, A_n with i=1nAi=N\bigcup_{i=1}^n A_i = \mathbb{N} such that whenever n1n-1 numbers are picked from n1n-1 of these sets, their sum belongs to the set that was left, i.e. the one among these nn sets from which a number was not picked.
    1. Let nn be a positive integer. The set {1,2,,3n}\{1, 2, \dots, 3n\} is divided in three disjoint sets A,B,CA, B, C. Is it always possible to find x,y,zx, y, z each belonging to one of these sets such that x+y=zx + y = z?
    1. Let S={x1,,xn}S = \{x_1, \dots, x_n\}. Fix some knk \le n and let TT be the set of all sums xi1+xi2++xikx_{i_1} + x_{i_2} + \dots + x_{i_k} where xi1,xi2,,xikx_{i_1}, x_{i_2}, \dots, x_{i_k} are distinct. Prove that TT contains at least k(nk)+1k(n-k) + 1 distinct elements.
    1. Assume 20002000 integers are given with 1000a1,,a20001000-1000 \le a_1, \dots, a_{2000} \le 1000 with sum equal to 11. Prove that there exists a subset of them with sum equal to 00.
    1. Let p>2p > 2 be a prime and a1,,ap2a_1, \dots, a_{p-2} integers with pak((ak)k1)p \nmid a_k((a_k)^{k-1}) for all kk. Prove that there is a subset of these integers such that its sum equals 2(modp)2 \pmod p.
    1. Let nn and a1<a2<<akna_1 < a_2 < \dots < a_k \le n be integers with lcm(ai,aj)>n\mathrm{lcm}(a_i, a_j) > n for all i,j,iji, j, i \ne j. Prove that i=1k1ai<32\sum_{i=1}^k \frac{1}{a_i} < \frac{3}{2}.
    1. Assume that a sequence x1,x2,x_1, x_2, \dots is such that 0<xn+1xn<1000 < x_{n+1} - x_n < 100. Prove that there exist indices a,ba, b such that xaxbx_a \mid x_b.

3. Homework

    1. In a subset SS of set {1,2,,2011}\{1, 2, \dots, 2011\} no two elements differ by 44 or by 77. What is the largest possible size of SS?
    1. Prove that among n+1n+1 different numbers chosen from {1,2,,2n}\{1, 2, \dots, 2n\} there exist two numbers such that one divides the other one.
    1. For a given number nn, determine mm; the size of biggest subset of {1,2,,2n}\{1, 2, \dots, 2n\} such that least common multiple of every two numbers in subset is at least mm.
    1. A sequence of integers xnx_n satisfies x1=1x_1 = 1 and xnxn+12nx_n \le x_{n+1} \le 2n for all integers nn. Prove that for every integer kk there exist indices a,ba, b such that xaxb=kx_a - x_b = k.
    1. Let a1<a2<<an<2na_1 < a_2 < \dots < a_n < 2n be integers such that none of them divides another one. Assume that for some kk, 3k<2n<3k+13^k < 2n < 3^{k+1}, prove that a12ka_1 \ge 2^k.
    1. Assume a1,,aka_1, \dots, a_k are distinct integers with gcd(ai,aj)n\gcd(a_i, a_j) \le n for each two indices i,ji, j. Prove that k2nk \le 2 \lfloor \sqrt{n} \rfloor.

Level 4 Problems

  • Given a non-negative integer kk, show that there are infinitely many positive integers nn such that the product of any nn consecutive integers is divisible by (n+k)2+1(n+k)^2+1.
  • Find all functions f:NNf: \mathbb{N} \to \mathbb{N} such that for all m,nNm,n \in \mathbb{N} holds f(mn)=f(m)+f(n)f(mn) = f(m) + f(n) and m+nf(m)+f(n)m+n \mid f(m) + f(n).
  • We call NN a fantastic number if it can be represented as a sum of different squares. Prove that there are 20222022 consecutive numbers such that 20162016 of them are fantastic.
  • Find all positive integers kk such that for every nNn \in \mathbb{N}, if there are kk factors (not necessarily distinct) of nn so that the sum of their squares is nn, then there are kk factors (not necessarily distinct) of nn so that their sum is exactly nn.
  • Suppose that AA is the set of all positive integers that can be written in form a2+2b2a^2+2b^2 (where a,bZa, b \in \mathbb{Z} and b0b \ne 0). Show that if pp is a prime number and p2Ap^2 \in A then pAp \in A.
  • We call a number nice if it can be represented as ab+ba^b+b for a,b>1a, b > 1. Prove that there are 20222022 consecutive numbers such that 20152015 of them are nice numbers.
  • Find all f:NNf: \mathbb{N} \to \mathbb{N} such that for all a,b,cNa, b, c \in \mathbb{N}, f(a)+f(b)+f(c)abbccaaf(a)+bf(b)+cf(c)3abcf(a)+f(b)+f(c)-ab-bc-ca \mid af(a)+bf(b)+cf(c)-3abc
  • Prove that there are 20222022 consecutive numbers with 1010 'power mean numbers' (Mn)(M_n) among them.
  • Find all primes pp and positive integers rr that satisfy the following equality pp+(p+1)p++(p+r)p=(p+r+1)pp^p + (p+1)^p + \dots + (p+r)^p = (p+r+1)^p
  • Find all polynomials fZ[x]f \in \mathbb{Z}[x], such that for each odd prime pp f(p)(p3)!+p+12f(p) \mid (p-3)! + \frac{p+1}{2}
آخر تحديث كان في