Parity · Integers

Total: 9
Reset
ARMO 2017, School Round, 10.2
ID: 42 🏷 ARMO 📅 2017 🎓 10 ★★★★☆☆☆☆☆☆ Easy
combinatorics number theory divisibility modular arithmetic pairing

Is it possible to pair all natural numbers from 1 to 800 such that the sum of each pair is divisible by 6?

No, it is not possible.

For the sum of two numbers to be divisible by 6, their remainders modulo 6 must complement each other to 6. Possible pairs of remainders are:

  • 0 and 0,
  • 1 and 5,
  • 2 and 4,
  • 3 and 3.

Thus, all numbers divisible by 6 (remainder 0) can only be paired with each other. Therefore, the number of such numbers must be even. However, in the range from 1 to 800, there are exactly ⌊800/6⌋ = 133 numbers divisible by 6 (these are the numbers 6, 12, ..., 798). Since 133 is odd, it is not possible to pair all 800 numbers with the required property.

ARMO 2018, District Round, 11.4
ID: 43 🏷 ARMO 📅 2018 🎓 11 ★★★★★☆☆☆☆☆ Medium
divisibility geometry number theory parity polygons integers

In the vertices of a 17-sided polygon, different integers are written (one in each vertex). Then all the numbers are simultaneously replaced with new ones: each number is replaced by the difference of the two numbers following it in a clockwise direction (subtracting the next from the neighboring one). Could the product of the resulting numbers be odd?

No.

Let the numbers around the circle be \(a_1, a_2, \, \ldots, \, a_{17}\). Then the new numbers will be \(a_2 - a_3, a_3 - a_4, \, \ldots, \, a_{17} - a_1, a_1 - a_2\), and their sum is 0.

If the sum of 17 numbers is even, then there is at least one even number among them (the sum of an odd number of odd numbers is odd). Thus, the product of these numbers is even.

Answer: No.

ARMO 2013, Regional Round, 10.1
ID: 46 🏷 ARMO 📅 2013 🎓 10 ★★★★★☆☆☆☆☆ Medium
number theory digits parity contradiction

Given natural numbers M and N, both greater than ten, consisting of the same number of digits, such that M = 3N. To obtain the number M, you add 2 to one of the digits of N and add an odd digit to each of the other digits. What digit could the number N end with?

The digit 6.

The number A = M – N = 2N is even. However, according to the condition, the number A is composed of odd digits and a two. Therefore, A ends with 2. Hence, the number N, which is half of A, ends with either 1 or 6.

If N ends with 1, doubling it does not cause a carry from the last to the second-to-last digit. Therefore, the second-to-last digit of A = 2N would be even, but it should be odd. Contradiction.

ARMO 2010, Regional Round, 10.1
ID: 45 🏷 ARMO 📅 2010 🎓 10 ★★★★★☆☆☆☆☆ Medium
combinatorics parity number theory circular arrangement proof contradiction

Neznaika wrote 11 natural numbers in a circle. For each pair of adjacent numbers, he calculated their difference (subtracting the smaller from the larger). Among the differences found, there were four ones, four twos, and three threes. Prove that Neznaika made a mistake somewhere.

Neznaika made a mistake because the sum of the differences cannot be even.

We record each of our differences with a positive sign if in the corresponding pair of numbers the larger number precedes the smaller one clockwise, and with a negative sign otherwise. We have 11 differences between a number and the next one clockwise; thus, the sum of all these numbers is zero, which means it is even. But this is impossible, since there are exactly seven odd numbers among them.

ARMO 2006, District Round, 9.5
ID: 44 🏷 ARMO 📅 2006 🎓 9 ★★★★★☆☆☆☆☆ Medium
parity number theory combinatorics problem solving

On the board, there is a product \(a_1a_2\ldots a_{100}\), where \(a_1, \ldots, a_{100}\) are natural numbers. Consider 99 expressions, each obtained by replacing one multiplication sign with an addition sign. It is known that exactly 32 of these expressions are even. What is the maximum number of even numbers among \(a_1, a_2, \ldots, a_{100}\) that could exist?

33 numbers.

Consider the leftmost even number \(a_i\) and the rightmost even number \(a_k\). Notice that all sums with indices from \(i\) to \(k - 1\) are even, and only they are (in sums with smaller indices, the first term is odd and the second is even; in sums with larger indices, the opposite is true).

Thus, \(k - i = 32\). The number of even numbers will be maximized if all numbers between \(a_i\) and \(a_k\) are also even. In this case, the number of even numbers will be 33.

ARMO 2011, Regional Round, 10.3
ID: 48 🏷 ARMO 📅 2011 🎓 10 ★★★★★★☆☆☆☆ Medium
combinatorics number theory parity sums digits

Given distinct natural numbers \( a_1, a_2, \, \ldots, \, a_{14} \). All 196 numbers of the form \( a_k + a_l \), where \( 1 \leq k, l \leq 14 \), are written on the board. Can it be that for every combination of two digits among the numbers on the board, there is at least one number ending with that combination (i.e., numbers ending with 00, 01, 02, \(\ldots\), 99 are found)?

It cannot.

Let there be \( a \) even numbers and \( b = 14 - a \) odd numbers among our 14 numbers. An odd number on the board can only appear as the sum of an even and an odd number, so there will be \( ab \) such numbers (each will be written twice). But \( 4ab \leq (a + b)^2 = 4 \cdot 49 \). Therefore, there will be at most 49 different odd numbers on the board; however, to satisfy the condition, there must be at least 50.

ARMO 2007, Final Round, 9.2
ID: 47 🏷 ARMO 📅 2007 🎓 9 ★★★★★★☆☆☆☆ Medium
fractions parity combinatorics number theory

On a board, 100 fractions are written such that the numerators are all the numbers from 1 to 100, each used exactly once, and the denominators are all the numbers from 1 to 100, each used exactly once. It turns out that the sum of these fractions is an irreducible fraction with a denominator of 2. Prove that it is possible to swap the numerators of two fractions so that the sum becomes an irreducible fraction with an odd denominator.

It is possible to swap the numerators of two fractions so that the sum becomes an irreducible fraction with an odd denominator.

Assume initially the sum included the fraction \( \frac{a}{2} \). We will show that in the original sum, there exists a fraction \( \frac{b}{c} \) with an odd denominator \( c \) such that the numbers \( a \) and \( b \) have different parities. Indeed, there are exactly 50 fractions with odd denominators, and the number \( a \) is not the numerator of any of them. Therefore, among the numerators of such fractions, at most 49 have the same parity as \( a \).

Now, swap the numerators \( a \) and \( b \). Do this in two steps: first, swap the numerator of the fraction with denominator 2 (the sum changes by an odd number \( a - b \) of halves and thus becomes an integer), and then swap the numerator of the fraction with denominator \( c \) (the sum changes by a fraction with an odd denominator, thus becoming a fraction with an odd denominator).

ARMO 2015, Final Round.
ID: 50 🏷 ARMO 📅 2015 🎓 10 ★★★★★★★☆☆☆ Hard
combinatorics number theory fractions parity modular arithmetic

Let \( n > 1 \) be a natural number. Consider the fractions \( \frac{1}{n}, \frac{2}{n}, \ldots, \frac{n-1}{n} \) and reduce each to its simplest form; denote the sum of the numerators of these fractions by \( f(n) \). For which natural \( n > 1 \) do the numbers \( f(n) \) and \( f(2015n) \) have different parity?

For all natural \( n > 1 \).

Let \( n = 2^t \cdot m \), where \( t \geq 0 \), and \( m \) is odd. We will prove that \( f(n) \) is even in exactly two cases: either \( n \) is odd and \( m \equiv 1 \pmod{4} \), or \( n \) is even and \( m \equiv 3 \pmod{4} \).

First method. Consider an arbitrary fraction \( \frac{k}{n} \). If \( k \) is divisible by \( 2^{t+1} \), then the numerator of this fraction after reduction will be even; otherwise, it will be odd. Among the numbers \( 1, 2, \ldots, n - 1 \), there are exactly \( \frac{m-1}{2} \) numbers divisible by \( 2^{t+1} \). Thus, in the sum \( f(n) \), there are exactly \( n - 1 - \frac{m-1}{2} \) odd terms. Therefore, \( f(n) \) is even if and only if the numbers \( n - 1 \) and \( \frac{m-1}{2} \) have the same parity, as required.

Second method. Suppose \( n \) is odd (i.e., \( t = 0 \)). Then the numerator of the fraction \( \frac{k}{n} \) does not change parity after reduction. Thus, the number of odd numerators will be \( \frac{n-1}{2} \), and \( f(n) \) is even if and only if \( \frac{n-1}{2} \) is even, which occurs when \( m \equiv 1 \pmod{4} \).

Suppose \( n \) is even (\( t > 0 \)). Among the fractions with denominator \( n \), there is a fraction equal to \( \frac{1}{2} \) contributing 1 to \( f(n) \). All other fractions are paired as \( \left(\frac{a}{n}, \frac{n-a}{n}\right) \). Since the sum of fractions in a pair is 1, after reduction, they become pairs of irreducible fractions with the same denominator \( \left(\frac{b}{d}, \frac{d-b}{d}\right) \). The contribution of such a pair to \( f(n) \) is \( d \), and if \( d \) is even, it does not affect the parity of \( f(n) \).

Thus, the parity of \( f(n) \) is opposite to the parity of a similar sum for fractions, i.e., the parity of \( f(m) \) (for \( m = 1 \), it is opposite to the parity of \( f(1) = 0 \)). This gives the required result.

Finally, note that the numbers \( n \) and \( 2015n \) have the same parity; moreover, for odd \( m \), the numbers \( m \) and \( 2015m \) leave different remainders when divided by 4. Therefore, the numbers \( f(n) \) and \( f(2015n) \) always have different parity.

ARMO 2011, Regional Round, 11.2
ID: 49 🏷 ARMO 📅 2011 🎓 11 ★★★★★★★☆☆☆ Hard
number theory integers inequality parity

Given 2011 non-zero integers. It is known that the sum of any one of them with the product of the remaining 2010 numbers is negative. Prove that if these numbers are divided into two groups in any way and the numbers in each group are multiplied, then the sum of the two resulting products will also be negative.

The sum of the products is negative.

Assume there is an even number of negative numbers among the given numbers. Then there is a positive number \(a\), and the product of all numbers except \(a\) is positive. This contradicts the condition. Therefore, there is an odd number of negative numbers among the given numbers.

Let \(x_1, x_2, \ldots, x_k\) and \(y_1, y_2, \ldots, y_m\) be two groups into which the given numbers are divided \((k + m = 2011)\). Exactly one of the two products \(x_1x_2\ldots x_k\) and \(y_1y_2\ldots y_m\) (specifically, the one with an odd number of negative factors) is negative; let \(x_1x_2\ldots x_k < 0\), \(y_1y_2\ldots y_m > 0\). Among the numbers \(x_1, x_2, \ldots, x_k\), there will be a negative one, say \(x_1 < 0\). Then \(x_2\ldots x_k > 0\), and thus \(x_2\ldots x_k \geq 1\) (since the numbers are integers). Therefore,

\(x_1x_2\ldots x_k + y_1y_2\ldots y_m \leq x_1 + y_1y_2\ldots y_mx_2\ldots x_k < 0.\)