Combinatorial number theory
1. Overview
Unlike in a previous lecture where we discussed various number theory theorems like 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
-
- Let be a digit number without a single 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 .
-
- Let be a set of natural numbers with elements such that none of elements of has a prime divisor bigger than . Prove that it is possible to pick four distinct elements of : such that for some integer .
-
- Assume that is a subset of such that the product of any three distinct elements of is not a square. What is the maximal possible cardinality of ?
-
- What is the maximal number of elements of that can be picked such that each pair of them is coprime?
-
- Let be integers. Prove that there exist different integers with .
-
- Is it possible to arrange numbers from to around circle such that for each two neighbours we have ?
-
- Let be a prime and let . Let such that no among them give the same residue modulo . Prove that if considered sums modulo of subsets of size of set - there must appear at least distinct sums.
-
- If is a prime number, prove that among integers there must be at least integers with sum divisible by .
-
- (Erdos-Ginzburg-Ziv theorem) For every positive integer , prove that among integers there exist integers whose sum is divisible with .
-
- Is there an such that it is possible to construct disjoint sets with such that whenever numbers are picked from of these sets, their sum belongs to the set that was left, i.e. the one among these sets from which a number was not picked.
-
- Let be a positive integer. The set is divided in three disjoint sets . Is it always possible to find each belonging to one of these sets such that ?
-
- Let . Fix some and let be the set of all sums where are distinct. Prove that contains at least distinct elements.
-
- Assume integers are given with with sum equal to . Prove that there exists a subset of them with sum equal to .
-
- Let be a prime and integers with for all . Prove that there is a subset of these integers such that its sum equals .
-
- Let and be integers with for all . Prove that .
-
- Assume that a sequence is such that . Prove that there exist indices such that .
3. Homework
-
- In a subset of set no two elements differ by or by . What is the largest possible size of ?
-
- Prove that among different numbers chosen from there exist two numbers such that one divides the other one.
-
- For a given number , determine ; the size of biggest subset of such that least common multiple of every two numbers in subset is at least .
-
- A sequence of integers satisfies and for all integers . Prove that for every integer there exist indices such that .
-
- Let be integers such that none of them divides another one. Assume that for some , , prove that .
-
- Assume are distinct integers with for each two indices . Prove that .
Level 4 Problems
- Given a non-negative integer , show that there are infinitely many positive integers such that the product of any consecutive integers is divisible by .
- Find all functions such that for all holds and .
- We call a fantastic number if it can be represented as a sum of different squares. Prove that there are consecutive numbers such that of them are fantastic.
- Find all positive integers such that for every , if there are factors (not necessarily distinct) of so that the sum of their squares is , then there are factors (not necessarily distinct) of so that their sum is exactly .
- Suppose that is the set of all positive integers that can be written in form (where and ). Show that if is a prime number and then .
- We call a number nice if it can be represented as for . Prove that there are consecutive numbers such that of them are nice numbers.
- Find all such that for all ,
- Prove that there are consecutive numbers with 'power mean numbers' among them.
- Find all primes and positive integers that satisfy the following equality
- Find all polynomials , such that for each odd prime
آخر تحديث كان في