** ****Problem 16- A bound regarding binomial coefficients**

For each define the binary entropy , and let a fixed integer. Show that the following inequality holds for all .

**Solution. **Substitute the explicit value of in the inequality, and just regroup to obtain the inequality . It means that we can reformulate the problem in the equivalent form: “*Let* *be positive integers with sum* , *then* ”. So, for every fixed we obtain that left hand side if this inequality is a function of the unique variable , since . We can show that attains its minimum at ,so that it will be enough to show that . Observe also that the function is symmetric with respect to .

*Case1*: for some . Fix , then , that is true if and only if : it can be rewritten as . Now it is well-known that the function is strictly increasing in , so that this inequality remains true if and only if , and in fact by construction . So, for the case even, we have to show that , that is for all positive integer .

*Case2*: for some . Just repeat the same ideas of previous lines: fix , then , that is true if and only if : it can be rewritten as . And, as before, it is enough that , and in fact by construction . So, for the case odd, we have to show that . Now multiply both members to , and we obtain: . Set and observe the following chain of inequalities: . We have shown that for the case odd, it is enough to prove that for all positive integer .

First, let’s verify manually that is greater than , defined as the maximum between and for all : *(C, k(C), h(C)):* { (1, 2, 1.3), (2, 6, 3.2), (3, 20, 9.1), (4,70 , 28.4), (5, 252, 93), (6, 924, 315), (7, 3432, 1092), (8, 12870, 3855), (9, 48620, 13797),(10, 184756, 49932),(11, 705432, 182361)}.

Note now that for all real the inequality holds, so that the whole problem can be summarized in for all positive integer .

Define now the sequence of of positive reals by . It is clear that such sequence is (strictly) decreasing, with . Integrating two times by part, also : we can conclude that:

, that implies . So, for the proof of our problem, it is enough that , that is ; using the weak inequalities and , it is enough that , that is . The proof is complete since we assumed . []

**Problem 17- A sum of prime powers is not a power of 2**

Find all such that ,where .

**Solution***.* We will prove that if is a solution that .

1. If then , so that .

2.If and then . If then in we have , so that , but is absurd. Otherwise, , and in we have : this is enough to find the other trivial solution .

3. If and then . Since we have that , and taking we obtain , absurd.

4. From now, we can suppose , so that implies that .

5. In we have that , so and .

6. In we have that , so .

7. In we have that but residues of are exactly , so that we can conclude that .

8. To sum up all observations in points 5,6,7 , we can reformulate the problem as “find all such that for some .

9. In we have that ; and since then also . Now residues of are exacty , and we are searching , that is equivalent to .

10. To sum up all observations in points 8,9 , we can reformulate the problem as “find all such that . We divide the rest of the solution in two cases:

PART 1.

11. Let’s find all solutions in the case , that is in non-negative integers.

12. The equation in point 11 is equivalent to , and we can see the trivial solution with that is . Let’s show that no other integer solutions exist.

13. Consider the 2-adic valuations: it is true that . And by the lifting lemma it is equal to , that implies , so .

14. Consider the equation in (after observing that ), and we obtain: that is equivalent to

15. To sum up points 13,14, the equation becomes equivalent to for some positive integers.

16. After observing that (that is equivalent to ), consider the equation of point 15 in : we have that and . This is a contradiction.

PART 2.

17. Now let’s show that in the case , the equation has no solutions.

18. In (the information in this point makes the difference from the previous part) we have . Now, since , we conclude that , that is equivalent to and .

19. Observe that and take the equation in , we have: . We can see directly by hand that residues of are exactly and residues of are . And we can see that is a solution if and only if .

20. Since we know that for point 18, then it is also true that . In particular if is a divisor of then is constant in .

21. In we have . Now and : complete residues of LHS are , and complete residues of RHS are .

22. Looking previous residues we can see that if is a solution modulo ( we can say that because ) then .

23. In noone of previous couples modulo we verify that , as requested in point 18. This is a contradiction. []

**Problem 18. A equation on 4 non negative integers.**

Solve the equation in nonnegative integers.

**Solution. **Since the equation is simmetric in , we can assume without loss of generality that .

Moreover, we must have : in fact, if then there exists a integer such that is a perfect non-trivial power. And it’s well known (working in ) that the unique solution is , that is , but or do not work.

If then , that is a contradiction. And, if then that implies , so if is a solution then and are coprime positive integers.

Also, looking the equation in and we deduce also that and .

If then and, as before, is never a non trivial perfect power.

If then, since , we have to verify if , and we have the solutions (and the simmetrical ).

If then, since , we have to verify only two cases: and , and both have no solutions. From now, we can assume .

Since then we can examine first cases (when is “big”): if for some then (this congruence is implies , so there exist such that and ). It means that :

– if then , but we already examined this case;

– if then , and . But and we have the solution and its simmetrical one.

– if then , and since we have to check only cases . But in both cases is not a integer, since is not a quadratic residue in . From now, we can assume that if then : it means that .

To sum, other than two previous solutions, if verify the original equation, then and , and .

If then and if and only if , that is a contradiction.

If then (that is implies ), or (that is , contradiction).

If then , that is a contradiction.

We proved that if is a solution (with ) then it belongs in . []

**Problem 19. Simmetric divisibilty**

Find all such that .

*Solution*. It’s clear that is a infinite class of solutions and that otherwise we must have . It holds also . Since then it holds also : divides . But , that’s a contradiction. []

**Problem 20. Even implies divisible by 8**

If are fixed such that is a perfect square, then is idivisible by .

*Solution*. Define the integer , then is a perfect square. Since is even, then for all . If in then . Otherwise , that’s our aim. []

**Problem 21. Sum of powers of 2 is a fixed integer**

Find all non negative integers such that .

*Solution*. It’s well-known that every positive integer has a unique binary representation. If is a fixed positive integer, then define the number of 1 that are in his binary representation. Since then . Now, if then and it means that . Instead, if and then : it means that if or if . In all previous cases . It means that if a triple solution exists then wlog . But since the binary representation is unique, then we must have and all his permutations. []

**Problem 22. Divisibility again**

Define . How many positive integers satisfy ?

*Solution*. Since and is or (but in all cases coprime with ), then by chinese remainder theorem we’ll have exactly a solution in the interval to the system of congruences: , where and . The number of way to choose and is evidently , and noone solution of them is exactly . Otherwise we have the cases in which for some , but we have to exclude the case that leads to the solution . So, we can conclude that there are exactly distinct positive integers such that . []

**Problem 23. A Easy equation in positive integers**

Find all such that .

*Solution.* Since then it implies that , and since then also , that’s . Now the following inequality holds: , that’s equivalent to : it means that , but also this couple does not satisfy the original equation, so there are no solutions. []

**Probem 24. Exponential equation with integers**

Find all such that .

*Solution*. We’ll show that if is a solution then .

– If then .

– If then .

– If then is a integer, since it’s difference of two integers. It means that a positive integer exists such that . The equation becomes , that’s . If then , and , implying that . Otherwise : then .

– If , then is a integer, since it’s difference of two integers. It means that a positive integers exists such that . The equation becomes . Since then implies that . The following chain of inequalities holds: , that’s a contradiction.

– If we have no solution since the equation becomes and is not defined in for all integer .

– If , then define the positive integers ; the equation becomes and it implies and . This system has no solution in positive *integers* . []