Maths Circle 10. Reduction – We Solve Problems

Maths Circle 10. Reduction

Ever found yourself looking at a problem and thinking it’s too difficult? Well, in today’s session we will think about how we can reduce the difficulty of a problem, making it easier to solve.
$\\
\\$
Quite often we have to deal with large values in mathematical problems. For example, we might be asked to prove something for a $1000\times1000$ board, or to play a game with two piles of 50 stones by some set of rules. It is not immediately obvious how to approach these questions.
$\\
\\$
With questions like these, a good piece of advice is to try to make them smaller whilst still maintaining the equivalency, eg: considering a $10\times10$ or $4\times4$ board instead of $1000\times1000$ and playing with 5 stones instead of 50.
$\\
\\$
We may not be able to solve the question straight away. How to make them smaller might not be evident or making them smaller not be helpful. Sometimes the answer to the question depends on using these specific values so changing them alters the answer. But, more often than not, working with smaller values helps us to understand the underlying logic of a problem, which then helps us work out a method for solving it that can then be applied to our question as well as other, similar, problems.
$\\
\\$
We can also work this in reverse. If you are stuck on a particular question think of other, similar, cases that you have solved before and apply that learning.
$\\
\\$
Most of the problems below are already divided into several parts; these are the ‘steps’ you need to take before you can make a general statement or prove a specific value. With these examples you need to learn how to choose what steps to take in order to prove something which is not evident from first-glance. Then you have to solve some questions in which you can practise choosing your own steps. But the goal is still to prove a statement for big values or in general.

Problems:

1.

Dissections, partitions, covers and tilings , Paritions of figures in segments

Cut an equilateral triangle into 4 smaller equilateral triangles. Then can another equilateral triangle be cut into 7 smaller equilateral triangles (triangles do not necessarily have to be identical)?

2.

Algebra and arithmetics , Arithmetic operations. Number identities

Back in the days when a young mathematician was even younger he could only draw digits “4” and “7”. While looking through the old notes his mother found one piece of paper on which he wrote the numbers with digit sums equal to 18, 22 and 26. Which numbers could be written on this piece of paper?

3.

Logic and set theory , Set theory and logic

Michael decided to buy new equipment for his daily exercises. There is a wide choice of barbells in the sports shop. All of them weigh an integer amount of kilograms. He recently got his job so he is a bit stingy and wants to buy as few barbells as possible. Michael has only one condition about the weights: he wants to be able to lift any integer amount of kilograms from 1 kg to 15 kg. What is the smallest amount of barbells he needs to buy and how many kilograms do they have to weigh?

4.

Dissections, partitions, covers and tilings , Paritions of figures in segments

Consider another equilateral triangle. Is it possible to cut it into (a) 9; (b) 16; (c) 28; (d) 2; (e) 42 smaller equilateral triangles (which are not necessarily identical)?$\\$
(f) Kyle claims he can cut an equilateral triangle into any number of smaller (not necessarily identical) equilateral triangles if this number is either greater than 8 and divisible by 3, or greater than 3 and has remainder 1 when divided by 3. Prove or disprove Kyle’s statement.$\\$
(g)* Let $n$ be a natural number greater than 5. Is it true one can cut an equilateral triangle into $n$ smaller equilateral triangles?

5.

Algebra and arithmetics , Arithmetic operations. Number identities

a) It seems that the young mathematician was making progress quite fast. On the back side of that piece of paper there are numbers with digits adding up to all natural numbers from 18 to 33. And yet all of them consist of only digits “4” and “7”. Make your own list of that kind.$\\$
(b) Is it true that any natural number greater than 17 can be equal to the digit sum of some number written with digits “4” and “7”?$\\$
(c) Now let’s try the same question for digits “5” and “8”. What values can you get if you consider the sum of the digits of a number written with the help of digits “5” and “8”?

6.

Logic and set theory , Set theory and logic

(a) Well, Michael was just a beginner that time. Don’t judge him much. He has made a considerable progress over the last month. Now he is planning to do any integer amount of kilograms from 1 kg to 31 kg. What is the smallest number of barbells one needs to have in order to do such weights?$\\$(b) Michael is doing just fine with weights up to 31 kg. Assume he is getting promotion soon, so he can afford a new set of weights. Can you already suggest which set will be the smallest if he decides to do all integer weights from 1 kg to 63 kg?$\\$(c) From 1 kg to 64 kg?$\\$(d) From 1 kg to 129 kg?

7.

Line or line segment as a locus , Locus

a) There are six points on a plane. No matter which five points you choose you can cross them with two lines but one cannot find two lines which cross all six of them. Does such configuration exist?$\\$
(b) One extremely successful businesswoman is planning to build a garden in her country house. She wants to have 10 garden beds and several lanes built. She requested her architect to organize the garden in such a way that for every nine beds there are three lanes passing by them (for each garden bed out of these nine beds there is a lane among the three lanes which passes by it). On top of that she demanded that there should not be three lanes which pass by all 10 garden beds. How can the poor architect satisfy this requirement? All lanes have to be straight.$\\$
(c) A neighbour of the businesswoman is inspired by her exotic demands. He decides to surpass her on this field. The neighbour plans to build 55 garden beds. They have to be joined by several lanes in such a way that for every 54 garden beds you can find nine lanes crossing them (for each garden bed out of these 54 beds there is a lane among the nine lanes which crosses this bed). Can you help the colleague of the architect? Again all the lanes have to be straight.

8.

Logic and set theory , Set theory and logic

You have a two pan set of scales. You have a black box which weighs a random integer amount of kilograms. (a) The weight of this box varies from 1 kg to 40 kg. Find a set of 4 integer weights which can be used to determine the weight of the box. You are allowed to put weights on both pans (even next to the black box).$\\$ (b) A red box can weight any integer amount of kilograms up to 100 kg. Is there a set of 5 integer weights adding up to 100 kg which allows us to determine the weight of the red box?

9.

Logic and set theory , Set theory and logic

(a) A traveller decided to stay in the motel. He has no money but he has a golden chain consisting of 7 links (the chain is not closed). The host agreed on one golden link to be the payment for one day of staying. The traveller wants to stay for the next 7 days. What is the smallest number of links he has to disunite to be able to make the payment every day? (Take into account that the host can give the change “in links” if he already got some from the traveller.)$\\$(b) Assume we have a chain consisting of 23 golden links and now the traveller has to spend 23 days in the motel. Is it enough to disunite 2 links to be able to make the daily payments? As before the host can give the change with the links he gets from the traveller.$\\$(c) Consider 24 links and 24 days now. Can we manage to make daily payments after we disunite some 2 links?$\\$($\textit{Comment:}$ In all questions above after we disunite the chain at some link in general we obtain three parts: the link itself, the left part of the chain and the right of the chain. Note that there might be no left or no right part.)

Print
My Problem Set reset
No Problems selected
Print Collection