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

  A square is divided into several convex polygons (more than `1`), each of which has a different number of sides. Prove that among these polygons there is a triangle.

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Combinatorics -> Graph Theory Geometry -> Plane Geometry -> Triangles Proof and Example -> Proof by Contradiction Geometry -> Solid Geometry / Geometry in Space -> Polyhedra Minimum and Maximum Problems / Optimization Problems

• Question

  A plane is colored with two colors (that is, every point on the plane is colored with one of these two colors). Prove that there exist two points on the plane at a distance of `1` such that they are both the same color.

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry -> Triangles Proof and Example -> Constructing an Example / Counterexample Proof and Example -> Proof by Contradiction

• Question

  Shlomi has a chessboard and a cube whose face size is the same as the size of a square on the board. Shlomi wants to paint the faces of the cube black and white, and then roll the cube across the board so that each time the face touching the board is the same color as the square it touches. The cube is supposed to pass through each square on the board exactly once. Can Shlomi do this? Justify or provide an example.

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Graph Theory Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction Combinatorics -> Colorings -> Chessboard Coloring

• Question

  The plane is divided by n lines and circles.

  Prove that the resulting map can be colored with two colors such that any two adjacent regions (separated by a segment or an arc) are colored with different colors.

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Induction (Mathematical Induction) Geometry -> Plane Geometry Proof and Example Combinatorics -> Colorings
  Sources:
  • Mink Exercises and Additional Competition Materials, 2018-2019, Exercise 4

• Question

  Inside a square with side length 1, `n>=101` points are marked, such that no three are collinear. A triangle is called marked if its vertices are marked points. Prove that the area of one of the marked triangles is less than `1/100`

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry Geometry -> Area Calculation
  Sources:
  • Mink Exercises and Additional Competition Materials, 2018-2019, Exercise 4

• Question

  Given an infinite grid whose vertices are colored with two colors, blue and red. Prove that there exist two horizontal lines and two vertical lines such that their four intersection points are colored with the same color.

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry Combinatorics -> Colorings
  Sources:
  • Zebra Exercises, 2018-2019, Exercise 1 Question 1

• The Grasshopper

  Consider an infinite grid of squares. A grasshopper sits on one of the squares. The grasshopper can jump two squares in any horizontal or vertical direction, and it can jump to the adjacent square diagonally. Can the grasshopper ever reach a square that is adjacent to its starting square by a side?

  Topics:

  Combinatorics -> Combinatorial Geometry Combinatorics -> Invariants Combinatorics -> Colorings -> Chessboard Coloring
  Sources:
  • Young Mathematician Olympiad, 2017-2018, Final, Grades 3-4 Question 2

• More Game Cubes

  Aviv has game cubes, where two opposite faces of each are painted red and the rest are blue.
  Aviv glued together a `3 xx 3 xx 3` cube from the game cubes. Then his friend Kfir came and calculated the total red area on the surface of the large cube.
  What is the largest result Kfir can get?

  Topics:

  Geometry -> Solid Geometry / Geometry in Space Combinatorics -> Combinatorial Geometry Minimum and Maximum Problems / Optimization Problems Combinatorics -> Colorings
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Stage A, Grades 5-6 Question 6

• 5 Lines, 8 Intersections

  Draw 5 lines such that there are exactly 8 points of intersection between them.

  Topics:

  Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Final, Grades 3-4 Question 1

• Star of David in a Circle

  Eight points are given on a circle. In how many different ways can a Star of David be drawn with vertices at these points?

  

  Note: A Star of David is a figure obtained when two triangles intersect and their sides create exactly 6 intersection points.

  Topics:

  Combinatorics -> Combinatorial Geometry Geometry -> Plane Geometry
  Sources:
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 7-8 Question 4