Proof and Example

This category emphasizes the core mathematical activities of constructing rigorous arguments (proofs) to establish general truths, and using specific instances (examples) to illustrate concepts, test conjectures, or find counterexamples. Questions may ask for either or both.

• Question

  In a certain country, there are more than 101 cities. The capital is connected by flight routes to 100 cities, and every city other than the capital is connected by flight routes to exactly 10 cities. It is given that from any city, it is possible to reach any other city (possibly not by a direct route). Prove that it is possible to close half of the flight routes leading to the capital such that the possibility of reaching any city from any other city is preserved.

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Graph Theory Logic -> Reasoning / Logic Proof and Example
  Sources:
  • Tournament of Towns, 1981-1982, Spring

• 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

• Cards with Digits

  Rachel has three cards with different digits, all of which are greater than 0. Rachel formed all possible three-digit numbers from these cards and calculated their sum.
  Prove that the sum is divisible by 3

  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules -> Divisibility Rules by 3 and 9 Logic -> Reasoning / Logic Proof and Example
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Final, Grades 3-4 Question 6
  • Young Mathematician Olympiad, 2019-2020, Final, Grades 5-6 Question 5

• Finite Division

  Find all integers x, y, z, w that satisfy `x^2+y^2=3z^2+3w^2`.

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Number Theory -> Division -> Parity (Even/Odd) Proof and Example Algebra -> Equations -> Diophantine Equations

• Question

  What is the smallest six-digit number with all different digits?

  Show hint

  Log in here to receive the hint
  Topics:

  Arithmetic Proof and Example -> Constructing an Example / Counterexample
  Sources:
  • problems.ru web site

• Question

  Three hedgehogs have three pieces of cheese weighing `5`, `8`, and `11` grams. A fox offers to help the hedgehogs divide the cheese equally. The fox can bite off one gram from each of two cheese pieces of its choice. Can the fox, using these actions, reach a state where it leaves the three hedgehogs with equal pieces of cheese?

  Topics:

  Arithmetic Algebra -> Word Problems Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Number Theory -> Division
  Sources:
  • problems.ru web site

• Question

  Can you divide `24` kilograms of nails into two parts of `15` and `9` kilograms using a balance scale without weights?

  Topics:

  Arithmetic Proof and Example -> Constructing an Example / Counterexample Algorithm Theory -> Weighing

• The broken chain

  There are five segments of a broken chain, each segment having three links. Moses wants to repair the chain. What is the minimum number of links he needs to open and close again to join all these segments together?

  Note: The chain is not circular!

  Topics:

  Algebra -> Word Problems Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Minimum and Maximum Problems / Optimization Problems

• Question

  Is it possible to arrange all the numbers from `1` to `100` in a row such that the difference between any two adjacent numbers is at least `50`? If so, provide an example; if not, prove why.

  Topics:

  Number Theory Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample
  Sources:
  • problems.ru web site

• 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