BRATISLAVA MATHEMATICS CORRESPONDENCE SEMINAR
Faculty of Mathematics and Physics of Comenius University
Union of Slovak Mathematicians and Physicists
Centre of Spare Time - IUVENTA

BMCS - Official solutions for the 1st fall series 1997/98

Math caviar

  1. This easy problem can be solved by various ways. Here is one of them:

    Pot First can Second can Ladle
    18
    0
    0
    0
    14
    4
    0
    0
    11
    7
    0
    0
    11
    3
    0
    4
    15
    0
    0
    3
    8
    7
    0
    3
    8
    6
    0
    4

    It is evident that we were able to put 6 liters into the first can without using the second one and thus we can repeat the process with the second can.

  2. Let's label the Red Hood's numbers as a1, a2, ... an. We will construct the following sums:
    s1 = a1,
    s2 = a1 + a2,
    ...
    sn = a1 + a2 + ... + an.
    If one of these sums were dividable by n, Red Hood would succeed. If no sum is dividable by n, all of these n sums will obtain one of (n-1) different remainders after division by n. According to Dirichlet principle, there will exist two sums sk and sq which will give the same remainder after division by n. Their positive difference will be dividable by n. Then
    sq - sk = ak+1 + ak+2 + ... + aq-1 + aq
    is a sum of several Red Hood's numbers and it is dividable by n. Since this process is valid for any Red Hood's numbers, she will always succeed.

  3. There exist 2n different integers constructed only from digits 5 and 8. Suppose that there are m integers on the Sherlock's notice. Let's change the first digit in each of them. None of the integers we will get could have been written on the notice, because each of them will differ only in 1 digit from one integer written on the notice. In addition, all new integers will be distinct, because they were created from distinct numbers. Yet we have 2m mutually distinct integers with n digits consisting of digits 5 and 8 and thus 2m 2n, m 2n-1.

    We will now prove that it is always possible to create 2n-1 integers. For n=1, we have one integer (e.g. 5) and 21-1 = 1. For n>1, we will append a digit to all integers with n-1 digits in such a way, that the new integers will have the odd number of occurences of digit 5. In this way, we will create 2n-1 integers which will differ in at least 2 digits. There could have been 2n-1 numbers on the Sherlock's notice.

  4. A. It is easy to see that the parity of the number of blue beads is invariant for all operations. Hence, it is not possible to construct a necklace with one blue bead from the necklace with 0 blue beads.

    B. In this case, the answer is yes. Just consider this sequence of operations:

    After appropriate number of iterations, we will get a necklace with 100 blue beads and one red bead.

    C. Take an arbitrary necklace N which can be constructed from "RR" and mark the numbers or red beads between blue beads as ci for i from [1,2n], where 2n is the number of beads on the necklace. Choose c1 arbitrarily and choose arbitrary orientation as well. We will prove, that alternating sum

    S(N)=-c1+c2-c3+...-c2n-1+c2n
    keeps divisibility/nondivisibility by 3 during all allowed operations. Since insertion and removal are inverse operations, we will consider only insertion. There are 3 possibilities (all others are equivalent with one of them):
    1. "RR" to "BRB": new bead into i-th segment just after cin-th bead:
      S(N')=-c1+c2-...+(-1)i mod 2[cin-1 - 1 + (ci - cin-1)] + ... + c2n
      S(N')-S(N)=(-1)i mod 2(-3)
      and so the remainder after division S(N) by 3 is not changed by this operation.
    2. "RB" to "BRR": new bead to the end of i-th segment:
      S(N')=-c1 + c2 - ... + (-1)i mod 2[ci-1 - (ci+1+2)] + ... + c2n
      S(N')-S(N) = (-1)i mod 2(-3),
      the remainder after division by 3 doesn't change,
    3. "MM" to "RRR": new bead between two blue (into a red segment of zero length), three consecutive seqments merge into one:
      S(N')=c1 + c2 - ... + (-1)i mod 2[ci + ci+2+3] + ... c2n
      S(N')-S(N) = (-1)i mod 23,
      the remainder is not changed.

    If we chose a different c1, the remainder after division S(N) by 3 would change only from 1 to 2 or vice versa - S(N)s would differ in the sign. For a necklace with all red beads, we define S(N) equal to S(N) of any necklace, which can be constructed from it by one operation (divisibility by 3 will not be ambiguous).

    S(N) mod 3 is 0 for the model "BB", and S(N) mod 3 is 2 for the model "RR". If there had been a sequence of operations leading from "RR" to "BB", there would have been an operation in this sequence, which would have resulted in the model with S(N) mod 3=0. As we have seen, such operation would have not been legal and such sequence doesn't exist.

  5. In this problem, it was supposed to prove that Mulder is false in all cases. Giving an example not compatible with his statements was not sufficient.

    Proof by contradiction. Let's assume there exists a case which Mulder was talking about. The square is divided into several parts. Perimeters of these parts consist of lines inside the square and perimeter of the large square. Each line belongs to at most 2 perimeters (some lines don't belong to any perimeter). Then, the sum of all perimeters is at most 40 (40=2.18+4). The sum of areas of parts is 1. Take one of these parts. Its perimeter is O and area S. In case its shape is not convex, its perimeter is not larger than the perimter of the smallest circumscribed rectangle. The area of this part must be smaller than the area of the circumscribed rectangle (see picture). If the rectangle has sides a and b, we get:

    O 2(a+b) >= 4.(ab) 4.(S).
    The middle inequality is implied from A-G inequality for a, b. If the shape of our part is convex, it is a rectangle or square and the inequality
    O 4. S
    can be derived analogically. According to our assumption, S < 1/100, and this is equivalent to S < S.1/10. Considering the previous inequality, we get: O 4.S > 40.S. If the perimeters of all parts are O1, O2, ..., Ok and areas are S1, S2, ..., Sk, then by adding the inequalities for each part separately, we will get:
    40 O1+O2+...+Ok > 40.(S1+S2+...+Sk) = 40.1
    and this is a contradiction.