Combinatorics, Combinatorial Geometry

Combinatorial Geometry explores the connections between combinatorics and geometry. It deals with problems about arrangements, configurations, and properties of discrete geometric objects (points, lines, polygons). Questions often involve counting, existence proofs, and geometric inequalities.

• Question

  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
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 1

• Question

  Is it possible to tile a `5xx5` board with dominoes?

  Note: The size of a board square matches the size of a domino square.

  Topics:

  Combinatorics -> Combinatorial Geometry Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Colorings -> Chessboard Coloring

• Question

  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
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 4

• Question

  Let M be a set of points in the plane. O is called a partial center of symmetry if it is possible to remove a point from M such that O is a regular center of symmetry of what remains. How many partial centers of symmetry can a finite set of points in the plane have? 
  V. Prasolov 

  Topics:

  Combinatorics -> Combinatorial Geometry Proof and Example -> Constructing an Example / Counterexample Geometry -> Plane Geometry -> Symmetry
  Sources:
  • Tournament of Towns, 1980-1981, Spring, Main Version, Grades 9-10 Question 2 Points 7

• Wolf and sheep

  The game takes place on an infinite plane. One player moves the wolf, and the other – 50 sheep. After a move by the wolf, one of the sheep makes a move, then the wolf again, and so on. In one move, the wolf or sheep moves no more than one meter in any direction. Can the wolf always catch at least one sheep, regardless of the initial configuration? 

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Combinatorics -> Game Theory Proof and Example -> Constructing an Example / Counterexample
  Sources:
  • Tournament of Towns, 1980-1981, Spring, Main Version, Grades 9-10 Question 5 Points 16

• Question

  Someone made `15` point-like holes in a carpet that is `4xx4` meters in size. Is it always possible to cut out a rug of size `1xx1` meter from the original carpet such that it has no holes?

  Show hint

  Log in here to receive the hint
  Topics:

  Geometry Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry
  Sources:
  • problems.ru web site

• Question

  Suppose two pyramids are tangent to each other if they have no common interior points and they intersect in a non-degenerate planar polygon. Is it possible for 8 pyramids in space to all be tangent to each other? 
  A. Angeles 

  Topics:

  Combinatorics -> Combinatorial Geometry Proof and Example -> Constructing an Example / Counterexample Geometry -> Solid Geometry / Geometry in Space -> Polyhedra
  Sources:
  • Tournament of Towns, 1980-1981, Spring, Main Version, Grades 11-12 Question 1 Points 7

• Question

  The game takes place on an infinite plane. One player moves the wolf, and another player moves K sheep. After the wolf's move, one of the sheep makes a move, then the wolf again, and so on. In one move, the wolf or a sheep cannot move more than one meter in any direction. Can the wolf always catch at least one sheep, regardless of the initial positions?

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Geometry -> Plane Geometry Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Minimum and Maximum Problems / Optimization Problems
  Sources:
  • Tournament of Towns, 1980-1981, Spring, Main Version, Grades 11-12 Question 2

• Stack of Papers

  Several identical rectangular sheets of paper lie on a table. It is known that the top sheet covers more than half the area of every other sheet. Is it necessarily possible to stick a pin into the table that will go through all these sheets?

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Area Calculation Geometry -> Plane Geometry -> Symmetry

• Question

  A number of lines and circles are drawn in the plane. Prove that it is possible to color the regions into which the plane is divided using two colors such that neighboring regions (those sharing a line segment or arc) are colored with different colors.

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Induction (Mathematical Induction) Geometry -> Plane Geometry Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Colorings