Arithmetic+ 01: UNIZOR.COM - Math+ & Problems - Arithmetic

Notes to a video lecture on http://www.unizor.com

Arithmetic 01


Problem A

Given n pieces of rope.
Some of them are cut into n smaller pieces.
Then, again, some of the obtained pieces are cut into n smaller one.
This process is repeated a few times and, as a result, the final number of pieces is N.
Prove that N−n is divisible by n−1.

Solution A

Assume, out of initial n pieces of rope we have chosen k₁ to cut each into n pieces.
Then, after the first cut we will have the total number of pieces equal to
N₁ = n − k₁ + n·k₁ =
= n + (n−1)·k₁
As we see, N₁−n is divisible by n−1.

Assume, out of obtained after the first step N₁ pieces of rope we have chosen k₂ to cut each into n pieces.
Then, after the second cut we will have the total number of pieces equal to
N₂ = N₁ − k₂ + n·k₂ =
= N₁ + (n−1)·k₂ =
= n + (n−1)·k₁ + (n−1)·k₂ =
= n + (n−1)·(k₁+k₂)
As we see, N₂−n is also divisible by n−1.

Obviously, it's easy to prove by induction that after s^th step the number of obtained pieces of rope will be
N_s = n + (n−1)·(k₁+k₂+...+k_s )
and N_s−n will be divisible by n−1, which is what's required to prove.


Problem B

One person thinks about some number from 0 to 1000.
Another person can ask questions about this number to determine it.
What is the minimum number of questions needed to find this number, if the answers can be either YES or NO?

Solution B

Considering the answers are YES or NO, one of the ways is to find the binary expression for the number.
Since the number is less than 1024=2¹⁰, it's sufficient to ask 10 questions about each binary digit.

So, the first question is: "Is the first digit in a binary representation of your number as 10 binary digits (including leading zeros) equal to 1? Based on the answer, we determine this first digit to be 1 or 0.
Then we repeat the same for the second binary digit etc.

Alternatively, the number can be guessed by multiple steps of dividing the group of all possible numbers into two approximately equal parts.
Then the first question should be: "Is your number greater than 500?".
If the answer is YES, the next question is "Is it greater than 750?", but if the answer is NO, the next question is "Is it greater than 250?".
And so on.


Problem C

There is a set of 100 numbers, each from 1 to 9.
The sum of these numbers is 789.
Is it possible to choose 70 numbers out of this set with a sum less than 500?

Solution C

If we select 70 numbers with a total sum of less than 500, the remaining 30 numbers must have sum not less than 789−500=289.
But the maximum sum of 30 numbers, each of which is from 1 to 9, is 9·30=270, which is insufficient to cover 289 needed to complete the total sum to 789.

Answer C
It is impossible to choose 70 numbers out of this set with a sum less than 500.


Problem D

A regular clock with large round face and 12 numbers for 12 hours is used for this problem.
A coin is placed onto each number of this clock - a total of 12 coins.
In one move two coins should be moved from their numbers into a neighboring ones, but one of these coins should move clockwise, while another - counterclockwise.

Is it possible to collect all coins on one number on the clock by performing th described moves?

Solution D

Assign a value to each position of coins as follows.
If there are n_i coins on number i, the value of this coin position is
V = Σ_i∈[1,12] i·n_i

Initially, when there is one coin per number on a clock, the total value is
V=1+2+3+4+5+6+
+7+8+9+10+11+12=78.

In one step one coin that is on number n and steps clockwise will increase the value V of a position by 1 except when it moves from number n=12 to n=1, in which case the value of a position will decrease by 11.

In one step one coin that is on number n and steps counterclockwise will decrease the value V of a position by 1 except when it moves from number n=1 to n=12, in which case the value of a position will increase by 11.

The combination of these two steps, which constitutes a single move, will either retain the same value of a position (for example, 3→4, 10→9) or increase the value by 12 (for example, 3→4, 1→12) or decrease the value by 12 (for example, 4→3, 12→1).

In any case, no matter how many moves we make, the value of a position V is changing by a number that is a multiple of 12.

But, if we consider the value of a position when all 12 coins are on the same clock number n, the value of a position is V=12·n - a multiple of 12.

Starting from an initial position value of 78 (not a multiple of 12) and changing this value by a number that is a multiple of 12 on each move, we will never come to a position whose value is a multiple of 12.

This proves the impossibility to gather all coins on the same clock number.