Reductio ad impossibile or Proof by contradiction

Theory

Imagine that there are two statements, A and B, of which only one is true and which are mutually exclusive.
Suppose we need to prove that the statement A is correct.
Proof by contradiction is a method of reasoning when, instead of directly proving the truth of statement A, it is proved that statement B is false, since it leads to a contradiction with established facts.

The simplest example: The sum of two numbers is 100. The first of them is 20 more than the second. Using counterintuitive reasoning, we can prove that the second number is 40.
Solution: Suppose that the second number is not equal to 40. Then it is either greater than 40 or less than 40. However, if the first number is greater than 40, then the second number is greater than 60 and their sum will be greater than 100, which contradicts the condition of the problem. If the first number is less than 40, then the second number is less than 60 and their sum will be less than 100, which also contradicts the conditions of the problem. Therefore, the second number is 40.

Problems

1. At the ball, all the ladies danced the first round of the waltz, while each military man danced with a blonde. Prove that every brunette danced the first round of the waltz with a civilian.

2. There are 15 balls of two colours lying in a circle. Prove that there are two adjacent balls of the same color.

3. Prove that in any company there are two people who have the same number of friends in this company.

4. The only people living on the island are knights who always tell the truth, and liars who always lie. At a meeting of islanders on the occasion of the island's birthday, some meeting participants said that among those gathered there were more liars than knights. Prove that there were both liars and knights at the meeting.
5.

a) Prove that if the product of two integers is even, then at least one of them is even.
b) Prove that if the product of two integers is divisible by 3, then at least one of them is divisible by 3.

6. All natural numbers are colored in five colors. Prove that there are a million numbers of the same color with the same sum of digits.

7. Can the product of two consecutive natural numbers be equal to the product of two consecutive even numbers?

8. Each of the voters in the elections puts the names of 10 candidates on the ballot. There are 11 ballot boxes at the polling station. After the elections, it turned out that each ballot box contains at least one ballot, and for any choice of 11 ballots, one from each ballot box, there will be a candidate whose name appears on each of the selected ballots. Prove that in at least one ballot box all ballots contain the name of the same candidate.
Additional

Subscribe to receive updates!

Be up-to-date with our recent updates, new problems and answers!

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.

Our courses

Where do you hold your classes?
We hold our classes online or on-site on Saturdays at our branch in Pimlico Academy, London.
You can find our timetable here.
What do you need to start learning online?
For lessons you only need a computer or phone with a microphone, camera and Internet access. Wherever you are - in London, Nottingham, New York or Bali - online lessons will be at hand.
When can I take the introductory lesson?
You can get acquainted with the school at any time convenient for you. To do this, just leave a request and sign up for a lesson.
I can't attend class, what should I do?
It is OK, it happens! Students have the opportunity to cancel a lesson up to 8 hours before the scheduled time without loss of payment. So you can reschedule it for a convenient time, and the teacher will have the opportunity to
I don't have much free time, will I have time to study?
Learning can take place at your own pace. We will select a convenient schedule and at any time we will help you change the schedule, take a break or adjust the program.
How long is one lesson?
All classes last 1 hour.
Hear from some of our amazing students who already achieved incredible results with us!
"Olympiad Maths Lessons helped me a lot to get the Gold medal in Junior Maths Challenge"
St. Paul's Student
"Thanks to the 'Data Science' and 'Coding in Python' lessons I got accepted to my dream university."
Michael
Data Science Student
Warwick University
"Great courses, which thoroughly explained topics beyond the capability of the GCSE answer sheet. Thanks so much."
Ivan
GCSE Student in Dubai
"Financial Mathematics! Best course to understand Python and Mathematics behind Finance!"
Gleb
VC Investor
"We got silver in PMC! Thanks George!"
Mum of St. Paul's Student
Prepare for the Primary Maths Challenge
"My daughter took a batch of 10 classes with George to understand Python with Turtle. I found George extremely knowledgeable and accessible."
Dad of Latymer School Student
Python with Turtle
We’re hiring!

Meet our team

Our teachers will tell you how to prepare for exams, help you cope with difficult tasks and win the Olympiad

They will tell you about the pitfalls of exams and the most common mistakes, and explain how to avoid them
George Ionitsa
Founder &
Teacher of Maths and Coding