Tournament of Towns, 1979-1980, Main, Spring

• Question 1

  On the circle, there are blue and red points. It is allowed to add a red point and change the colors of its neighboring points or remove a red point and change the colors of its neighboring points (it is not allowed to leave fewer than 2 points on the circle). Prove that it is impossible to move, using only these operations, from a circle with two red points to a circle with two blue points.
  K. Kaznvosky

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Algebra Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Set Theory Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Colorings -> Chessboard Coloring

• Question 2

  An `N×N` table is filled with numbers such that all rows are distinct (differing in at least one position). Prove that it is possible to delete a column such that in the remaining table all rows are also distinct.
  (a) Hint

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Proof and Example -> Proof by Contradiction

• Question 3

  Let a₁, a₂, ..., a₁₀₁ be a permutation of 2, 3, 4, ..., 102. Find all permutations such that a_i is divisible by i for all i.

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures

• Question 4

  In space, there are 30 non-degenerate vectors. Prove that there are at least 2 such that the angle between them is no greater than 45 degrees. 
  A. Tulpigo

  Topics:

  Geometry -> Trigonometry Geometry -> Spherical Geometry Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry -> Angle Calculation Geometry -> Vectors

• Question 5

  Given a convex quadrilateral ABCD. Each of its sides is divided into K equal parts. Points on side AB are connected to corresponding points on CD, and points on BC are connected to points on DA, creating K² smaller quadrilaterals. From these, K quadrilaterals are chosen such that any two quadrilaterals are separated by at least one line connecting AB and CD, and one line connecting BC and DA. Prove that the sum of the areas of these quadrilaterals is S_ABCD/K. 
  By A. Angans. 

  Topics:

  Geometry -> Plane Geometry Geometry -> Area Calculation Geometry -> Vectors

• Question 6

  In a square with side length 1, a finite number of segments parallel to the sides of the square were drawn, with a total length of 18 (they can intersect). Prove that among the parts into which the square is divided by the segments, there is a part with an area of at least 0.01. 
  A. Engenes, A. Brazins 

  Topics:

  Geometry -> Plane Geometry Geometry -> Area Calculation Algebra -> Inequalities Proof and Example -> Proof by Contradiction