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

  What is the maximum number of chess kings that can be placed on an `8xx8` board such that they do not threaten each other?

  Topics:

  Combinatorics -> Pigeonhole Principle Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Minimum and Maximum Problems / Optimization Problems Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry

• Question

  What is the maximum number of rooks that can be placed on an `8xx8` board so that they do not threaten each other?

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Minimum and Maximum Problems / Optimization Problems

• Question

  Shlomi has a flat box with a size of `5xx5` centimeters. Shlomi claims that any rectangle that can be stored in this box must have all its sides smaller than 5 centimeters. Is he right?

  Topics:

  Proof and Example -> Constructing an Example / Counterexample Geometry -> Plane Geometry -> Pythagorean Theorem

• Question

  In the magical land, there are only two types of coins: `16` LC (Magical Pounds) and `27` LC. Is it possible to buy a notebook that costs one Magical Pound and receive exact change?

  Topics:

  Proof and Example -> Constructing an Example / Counterexample Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM) -> Euclidean Algorithm Number Theory -> Division Algebra -> Equations -> Diophantine Equations

• Question

  Given `50` distinct natural numbers between `1` and `100`. It is known that no two of these numbers sum to `100`. Is it necessarily true that one of these numbers must be a perfect square?

  Topics:

  Number Theory -> Prime Numbers Arithmetic Combinatorics -> Pigeonhole Principle Combinatorics -> Matchings Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Set Theory Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction

• Question

  Every evening, Yuval finishes work at a random time and arrives at a bus stop. At this station, two buses stop: number `7`, which goes to Yuval's house, and number `13`, which goes to the house of his friend Shlomi. Yuval gets on the first bus that arrives and, depending on that, goes to Shlomi's or home.

  After a while, Yuval notices that after work, he goes to Shlomi's about twice as often as he goes home. He deduced from this that bus number `13` arrives twice as frequently as bus number `7`.

  Is Yuval necessarily correct?

  Show hint

  Log in here to receive the hint
  Topics:

  Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Probability Theory Logic -> Reasoning / Logic -> Paradoxes

• Three Runners

  Three runners, A, B, and C, ran a hundred-meter race together several times. The judge claims that A finished the race before B in more than half the races, B finished before C in more than half the races, and C finished before A in more than half the races.

  Is this possible?

  Topics:

  Proof and Example -> Constructing an Example / Counterexample Logic -> Reasoning / Logic -> Paradoxes

• Do All Horses Have the Same Color?

  Shlomi claims to have proven by induction that in every herd, all horses are the same color:

  If there is one horse, then it is the color of itself - thus we have shown that the base case of induction holds.

  For the inductive step, we number the horses from `1` to `n`. According to the inductive hypothesis, the horses numbered from `1` to `n-1` are all the same color. Similarly, the horses numbered from `2` to `n` are also all the same color. And because the colors of the horses from `2` to `n-1` are fixed and cannot change depending on how we assigned them to one group or another, then the horses `1` and `n` must also be the same color.

  Did Shlomi make a mistake in his proof? If so, find the mistake.

  Topics:

  Combinatorics -> Induction (Mathematical Induction) Proof and Example -> Constructing an Example / Counterexample Logic -> Reasoning / Logic -> Paradoxes

• Question

  Given the sequence `1 , 1/2 ,1/3 ,1/4 ,1/5,...`, does there exist an arithmetic sequence composed of terms from the aforementioned sequence?

  1. Of length 5

  2. Of any length

  Show hint

  Log in here to receive the hint
  Topics:

  Number Theory -> Modular Arithmetic / Remainder Arithmetic -> Divisibility Rules Proof and Example -> Constructing an Example / Counterexample Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence Arithmetic -> Fractions Number Theory -> Greatest Common Divisor (GCD) and Least Common Multiple (LCM)
  Sources:
  • Tournament of Towns, 1981-1982, Spring

• Cutting

  What is the largest number of rectangles of size `2 times 5`  that can be cut from a `9 times 9` square?

  Topics:

  Geometry -> Area Calculation Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Combinatorial Geometry -> Cut a Shape / Dissection Problems Combinatorics -> Combinatorial Geometry -> Grid Paper Geometry / Lattice Geometry
  Sources:
  • Young Mathematician Olympiad, 2018-2019, Stage A, Grades 3-4 Question 1
  • Young Mathematician Olympiad, 2018-2019, Stage A, Grades 5-6 Question 1