Proof and Example, Constructing an Example / Counterexample

This involves finding a specific instance that satisfies a given set of conditions (an example) or one that disproves a general statement (a counterexample). It's a crucial skill for understanding mathematical claims. Questions directly ask for such constructions.

• 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

• Question

  The numbers `1,2,3,4,5` are written at the vertices of a regular pentagon, with each number at exactly one vertex. A trio of vertices is called successful if it forms an isosceles triangle, where the number at its apex is greater than the numbers at the other two vertices, or where the number at its apex is smaller than the numbers at the other two vertices.

  Find the maximum number of successful trios that can exist.

  Show hint

  Log in here to receive the hint
  Topics:

  Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Geometry -> Plane Geometry -> Symmetry Minimum and Maximum Problems / Optimization Problems

• Ten-Digit Number

  Yael writes ten-digit numbers in whose decimal representation each of the digits `0, 1, 2, 3, 4, 5, 6, 7, 8, 9` appears exactly once.
  In the numbers that Yael writes, the difference between any two adjacent digits is at least 2. What is the smallest number Yael can write?
   

  Topics:

  Number Theory Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Stage A, Grades 3-4 Question 3
  • Young Mathematician Olympiad, 2019-2020, Stage A, Grades 5-6 Question 1

• The Round Table

  Around a round table are 12 chairs, with knights sitting on some of them. Arthur wants to join the meeting,
  and it turns out that no matter where he sits, someone is definitely sitting next to him.
  What is the smallest number of knights that can be around the table to ensure this is true? (not including Arthur)

  Topics:

  Combinatorics -> Pigeonhole Principle Logic -> Reasoning / Logic Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2019-2020, Stage B, Grades 3-4 Question 1

• Colorful Street 2

  There are 15 houses along the street, colored red, blue, and green. There is at least one house of each color.
  Between any two blue houses there is a red house. Between any two green houses there is a blue house.
  What is the largest possible number of green houses?
  Note: The street is straight, and all houses are located on one side of the street.

  Topics:

  Combinatorics -> Pigeonhole Principle Proof and Example -> Constructing an Example / Counterexample Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures
  Sources:
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 5-6 Question 5
  • Young Mathematician Olympiad, 2020-2021, Stage A, Grades 7-8 Question 6