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

__Arithmetic 01__

*Problem A*

Given

*pieces of rope.*

**n**Some of them are cut into

*smaller pieces.*

**n**Then, again, some of the obtained pieces are cut into

*smaller one.*

**n**This process is repeated a few times and, as a result, the final number of pieces is

*.*

**N**Prove that

*is divisible by*

**N−n***.*

**n−1***Solution A*

Assume, out of initial

*pieces of rope we have chosen*

**n***to cut each into*

**k**_{1}*pieces.*

**n**Then, after the first cut we will have the total number of pieces equal to

**N**

= n + (n−1)·k_{1}= n − k_{1}+ n·k_{1}== n + (n−1)·k

_{1}As we see,

*is divisible by*

**N**_{1}−n*.*

**n−1**Assume, out of obtained after the first step

*pieces of rope we have chosen*

**N**_{1}*to cut each into*

**k**_{2}*pieces.*

**n**Then, after the second cut we will have the total number of pieces equal to

**N**

= N

= n + (n−1)·k

= n + (n−1)·(k_{2}= N_{1}− k_{2}+ n·k_{2}== N

_{1}+ (n−1)·k_{2}== n + (n−1)·k

_{1}+ (n−1)·k_{2}== n + (n−1)·(k

_{1}+k_{2})As we see,

*is also divisible by*

**N**_{2}−n*.*

**n−1**Obviously, it's easy to prove by induction that after

*step the number of obtained pieces of rope will be*

**s**^{th}

**N**_{s}= n + (n−1)·(k_{1}+k_{2}+...+k_{s})and

*will be divisible by*

**N**_{s}−n*, which is what's required to prove.*

**n−1***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

*, it's sufficient to ask*

**1024=2**^{10}*questions about each binary digit.*

**10**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

*? Based on the answer, we determine this first digit to be*

**1***or*

**1***.*

**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

*?", but if the answer is NO, the next question is "Is it greater than*

**750***?".*

**250**And so on.

*Problem C*

There is a set of

*numbers, each from*

**100***to*

**1***.*

**9**The sum of these numbers is

*.*

**789**Is it possible to choose

*numbers out of this set with a sum less than*

**70***?*

**500***Solution C*

If we select

*numbers with a total sum of less than*

**70***, the remaining*

**500***numbers must have sum not less than*

**30***.*

**789−500=289**But the maximum sum of

*numbers, each of which is from*

**30***to*

**1***, is*

**9***, which is insufficient to cover*

**9·30=270***needed to complete the total sum to*

**289***.*

**789***Answer C*

It is impossible to choose

*numbers out of this set with a sum less than*

**70***.*

**500***Problem D*

A regular clock with large round face and

*numbers for*

**12***hours is used for this problem.*

**12**A coin is placed onto each number of this clock - a total of

*coins.*

**12**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

*coins on number*

**n**_{i}*, the value of this coin position is*

**i***Σ*

**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+7+8+9+10+11+12=78

In one step one coin that is on number

*and steps clockwise will increase the value*

**n***of a position by*

**V***except when it moves from number*

**1***to*

**n=12***, in which case the value of a position will decrease by*

**n=1***.*

**11**In one step one coin that is on number

*and steps counterclockwise will decrease the value*

**n***of a position by*

**V***except when it moves from number*

**1***to*

**n=1***, in which case the value of a position will increase by*

**n=12***.*

**11**The combination of these two steps, which constitutes a single move, will either retain the same value of a position (for example,

*) or increase the value by*

**3→4, 10→9***(for example,*

**12***) or decrease the value by*

**3→4, 1→12***(for example,*

**12***).*

**4→3, 12→1**In any case, no matter how many moves we make, the value of a position

*is changing by a number that is a multiple of*

**V***.*

**12**But, if we consider the value of a position when all

*coins are on the same clock number*

**12***, the value of a position is*

**n***- a multiple of*

**V=12·n***.*

**12**Starting from an initial position value of

*(not a multiple of*

**78***) 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***.*

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