Combinatorics, Induction (Mathematical Induction)
Mathematical Induction is a proof technique used to establish that a statement is true for all natural numbers (or an infinite sequence starting from some integer). It involves a base case and an inductive step. Questions require constructing inductive proofs for formulas, properties, or statements.
-
Question
In Wonderland, there are `n` cities, and every two of them are connected by a road. The roads meet only in the cities (there are no junctions outside the cities). A wicked magician wants to turn all the roads into one-way streets in such a way that if you leave any city, you can't return to it anymore.
a. Prove that the wicked magician can do this.
b. Prove that there exists a city from which one can reach any other city, and that there exists a city from which it is impossible to leave at all.
c. Prove that there exists a path that passes through all the cities and there is only one such path.
-
Question
Given a positive integer N, consider the following process: Let `S(N)` denote the sum of the digits of N. Take the sum of the digits of `S(N)`. Repeat this operation until a single-digit number is obtained. We call the number of times we performed the above process until we obtained a single-digit number the "depth" of N. For example, the depth of 49 is `S(49)=13 -> S(13)=4`, the operation was performed twice (and the depth of 45 is 1).
a) Prove that for every number N there is indeed a finite depth, that is, a single-digit number is always obtained at some stage of the process.
b) Let `x(n)` denote the minimum number (with the smallest value) with depth N. Find the remainder of `x(5776)` when divided by 6. Justify your answer!
c) Find the remainder of the number `x(5776) - x(5708)` when divided by 2016. Justify your answer!
Sources:Topics:Number Theory -> Modular Arithmetic / Remainder Arithmetic Combinatorics -> Induction (Mathematical Induction) Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence- Gillis Mathematical Olympiad, 2015-2016 Question 3
-
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.
-
Question
Given a real number `a` such that `a+1/a` is an integer. Prove that `a^n+1/a^n` is also an integer for every natural number `n`.
-
Question
The following numbers are written on the board: `1, 2, 3, …, 2016, 2017`. In one move, it is allowed to choose a pair of numbers written on the board, erase them, and write their (positive) difference in their place. After several such operations, a single number remains on the board. Is it possible that this is zero?
Topics:Arithmetic Combinatorics -> Invariants Combinatorics -> Induction (Mathematical Induction) Number Theory -> Division -> Parity (Even/Odd) Algebra -> Sequences -> Arithmetic Progression / Arithmetic Sequence Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction -
26 Coins
Given `26` coins that look identical. One of the coins is counterfeit, and it weighs less than a regular coin. How can you find the counterfeit coin using three weighings on a balance scale without weights?
-
80 Coins
Given `80` coins that look identical. One of the coins is counterfeit and weighs less than a regular coin. How can you find the counterfeit coin using four weighings on a balance scale without weights?
-
Question
Prove that
`1+3+5+...+(2n-1)=n^2`
-
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.
-
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.
Sources: