Proof and Example, Proof by Contradiction
Proof by contradiction (reductio ad absurdum) is an indirect proof technique. It assumes the negation of the statement to be proven is true, and then derives a logical contradiction from this assumption, thereby establishing the original statement's truth. Questions require applying this method.
-
Circle of Liars - The Truth Claim
In a circle, `n` people are seated, each of whom is either a liar or a truth-teller.
The people are looking towards the center of the circle. A liar always lies, and a truth-teller always tells the truth.
Each of the people knows exactly who is a liar and who is a truth-teller.
Each of the people says that the person sitting two places to their left (that is, next to the person sitting next to them), is a truth-teller.
It is known that in the circle there is at least one liar, and at least one truth-teller.
a. Is it possible that `n = 2017`?
b. Is it possible that `n = 5778`?
(Solution format: "word, word" for example "cat, puppy")
Sources:Topics:Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Combinatorics -> Case Analysis / Checking Cases -> Processes / Procedures Proof and Example -> Proof by Contradiction Logic -> Truth-tellers and Liars Problems- Gillis Mathematical Olympiad, 2017-2018 Question 1
-
Cyclic Quadrilaterals
Given two triangles ACE, BDF
intersecting at 6 points: G,H,I,J,K,L
as shown in the figure. It is given that in each of the quadrilaterals
EFGI, DELH, CDKG, BCJL, ABIK a circle can be inscribed.
Is it possible that a circle can also be inscribed in quadrilateral FAHJ?
Sources:Topics:Geometry -> Solid Geometry / Geometry in Space Geometry -> Plane Geometry -> Circles Algebra -> Equations Algebra -> Inequalities Proof and Example -> Proof by Contradiction Geometry -> Plane Geometry -> Angle Calculation- Gillis Mathematical Olympiad, 2019-2020 Question 5
-
Factoring and Using the Formula
An interesting formula is `x^n-1=(x-1)(x^{n-1}+x^{n-2}+...+x+1)`.
A: Use it to factor the expression `a^n-b^n`.
B: Factor the expression `a^n+b^n` for any odd integer n.
C: Prove that if `2^n-1` is prime, then n is also prime.
D: Prove that if `2^n+1` is prime, then n is necessarily a power of 2, which is equivalent to `n=2^m`
Sources: -
Finite Division
Find all integers x, y, z, w that satisfy `x^2+y^2=3z^2+3w^2 `.
Sources: -
Sets in the Plane
A. Does there exist a set A in the plane such that its intersection with every circle contains exactly two points?
B. Does there exist a set B in the plane such that its intersection with every circle of radius 1 contains exactly two points?
Sources:Topics:Geometry -> Plane Geometry -> Circles Proof and Example -> Constructing an Example / Counterexample Set Theory Proof and Example -> Proof by Contradiction Minimum and Maximum Problems / Optimization Problems- Grossman Math Olympiad, 2006 Question 3
-
Hexagonal Tiling
Given two types of tiles. The shape of each tile of the first type is a regular hexagon with a side of length 1. The shape of each tile of the second type is a regular hexagon with a side of length 2. An unlimited supply of tiles of each type is given. Is it possible to tile the entire plane using these tiles, using both types of tiles?
Sources:Topics:Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction Geometry -> Plane Geometry -> Angle Calculation- Grossman Math Olympiad, 2006 Question 4
-
Triangle Side Lengths
Let `n > 2` be an integer, and let ` t_1,t_2,...,t_n` be positive real numbers such that
`(t_1+t_2+...+t_n)(1/t_1 + 1/t_2 + ... + 1/t_n) < n^2+1`
Prove that for all i,j,k such that `1<=i<j<k<=n`, the triple of numbers `t_i,t_j,t_k` are the side lengths of a triangle.
Sources:Topics:Geometry -> Plane Geometry -> Triangles Algebra -> Inequalities Proof and Example -> Proof by Contradiction Geometry -> Plane Geometry -> Triangle Inequality- Grossman Math Olympiad, 2006 Question 5