mathspp.com feed Stay up-to-date with the articles on mathematics and programming that get published to mathspp.com. 2023-04-28T11:24:36+02:00 Rodrigo Girão Serrão https://mathspp.com/blog/problems Problem #063 – arbitrarily many primes in arbitrarily big intervals https://mathspp.com/blog/problems/arbitrarily-many-primes-in-arbitrarily-big-intervals 2023-04-12T10:31:44+02:00 2023-01-29T00:00:00+01:00

Can you prove that there are arbitrarily many primes in arbitrarily big intervals?

# Problem statement

The problem statement asks you to prove that for any positive integer number $$k$$ you can think of, there will be a certain lower bound $$n_0$$ (that depends on $$k$$) such that for any integer $$n \geq n_0$$, there is an interval of length $$n$$ that contains exactly $$k$$ primes. (When we talk about the length of the interval, we are talking about how many integers it contains.)

If the statement confused you a bit, that is ok. Let me rephrase it.

You and I will play a game. I will think of a positive integer $$k$$. Now, your job is to come up with another positive integer $$n_0$$ such that, if I pick a number $$n$$ greater than $$n_0$$, you can always find an interval of size $$n$$ that contains $$k$$ primes.

For example, if I thought of $$k = 5$$, you could not pick $$n_0 = 4$$. Why not? Because if I pick $$n = 4$$, there is no interval of length $$4$$ that contains $$5$$ prime numbers... Especially because an interval of length $$4$$ contains only $$4$$ integers!

This problem was posed to me by my mathematician cousin and I confess that worried me a bit. Funnily enough, the problem has a surprisingly simple solution. (I am not saying you will get there easily. I am just saying that once you do, you will realise the solution was not very complicated.)

Remember:

• there are infinitely many primes; however
• they become scarcer and scarcer the further you go down the number line.

# Solvers

Congratulations 🎉 to everyone who managed to solve this problem: Congratulations to you if you managed to solve this problem correctly! If you did, feel free to

• Rodrigo G. S., Portugal 🇵🇹 (<- example);

If you managed to solve this problem, you can add your name to the list! You can also email me your solution and we can discuss it.

# Solution

A thing I like about this problem is that not only can you prove that interesting statement about the prime numbers, but you can also determine exactly what the lower bound $$n_0$$ is.

Let us say that $$p_k$$ is the $$k$$-th prime. Then, if we set $$n_0 = p_k$$, we are good to go. Let me show you why.

Suppose that $$n$$ is any integer $$n \geq n_0$$. Then, the interval $$[1, n]$$ contains $$p_k$$ in it. Why? Because $$p_k = n_0$$ and $$n \geq n_0$$.

So, the interval $$[1, n]$$ contains $$k$$ or more prime numbers. If it contains $$k$$ prime numbers, we just found our interval of length $$n$$ that contains exactly $$k$$ primes. If it contains more than $$k$$ primes, we must do something about it.

If the interval $$[1, n]$$ contains more than $$k$$ prime numbers, then we start sliding the interval to the right, like so:...

]]>
Problem #062 – sliding coins https://mathspp.com/blog/problems/sliding-coins 2023-04-12T11:13:18+02:00 2022-06-12T00:00:00+02:00

Can you align all of the coins on the right edge of the board?

# Problem statement

The diagram above shows a 3 by 4 grid with 3 coins, one per row and one per column, such that the rightmost column of the grid is empty.

You are allowed to slide the coins to the columns on their right, but the coins can never leave the board (nor can they be moved back to the left). Also, you always have to move two coins at a time.

Thus, this is a legal move: A legal move sliding the top two coins one slot to the right.

But moving a single coin, such as in the diagram below, is not allowed: An illegal move that slides only one coin to the right.

Your objective is to reach this position:

Can you do it?

What if you extend the board two columns to the left and two rows up, and add another two coins along the diagonal?

This is an adaptation of a problem from the book “Algorithmic Puzzles” by Anany Levitin and Maria Levitin.1

# Solvers

Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:

• David H., Taiwan;

Know how to solve this? Join the list of solvers by emailing me your solution!

# Solution

The solution to this problem will be shared when this problem has been live for approximately two weeks, which should be in late June.

Don't forget to subscribe to the newsletter to get bi-weekly problems sent straight to your inbox.

1. This is an Amazon Affiliate link and I may earn a commission if you purchase the book. This comes at no extra cost to you.

]]>
Problem #061 – flower garden https://mathspp.com/blog/problems/flower-garden 2022-06-12T16:59:03+02:00 2022-05-22T00:00:00+02:00

Three mathematicians discuss a beautiful flower garden and the coloured flowers within.

# Problem statement

Three mathematicians were discussing a beautiful flower garden. The first mathematician said:

“It's a beautiful garden. All flowers are either red, yellow, or blue... And whatever three flowers you pick, one of them is bound to be red.”

The second mathematician said:

“It is indeed a beautiful garden! There are red flowers, yellow flowers, and blue flowers! I also noticed that, whatever three flowers you pick, one of them is bound to be yellow.”

The third mathematician, who had never been to the garden, remarked:

“That's interesting! If that's true, I can say that, whatever three flowers I pick, one of them is bound to be blue!”

The first two mathematicians glanced at each other and smiled.

Is the third mathematician right? Or wrong? Why?

This problem is from the amazing [book “To Mock a Mockingbird”][mock-mockingbird] by the mathematician Raymond Smullyan.1

# Solvers

Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:

• David H., Taiwan;
• Christ van W., The Netherlands;
• David R., Mexico;
• Michał D., Poland;

Know how to solve this? Join the list of solvers by emailing me your solution!

# Solution

The third mathematician is right.

The first sentence of each mathematician establishes that all flowers in the garden are one of three colours (red, yellow, blue) and that all colours are represented; that is, there is at least one red flower, at least one yellow flower, and at least one blue flower.

Then, the first mathematician says that whatever three flowers you pick, one is bound to be red. This means that the garden cannot contain three or more flowers that are not red. After all, if there were, say, two yellow flowers and one blue flower, you could pick those three and there wouldn't be a red flower in there.

At the same time, we know there has to be at least one yellow flower and one blue flower, so we conclude the garden has an unknown number of red flowers, one yellow flower, and one blue flower.

Then, the second mathematician speaks! From their remark, we could make a similar independent conclusion: the garden has an unknown number of yellow flowers, one red flower, and one blue flower.

Thus, if we combine the two conclusions, we get that the garden has three flowers only:

• one red flower;
• one yellow flower; and
• one blue flower.

Therefore, the third mathematician is also right: whatever three flowers you pick, one is bound to be blue.

Don't forget to subscribe to the newsletter to get bi-weekly problems sent straight to your inbox.

1. This is an Amazon Affiliate link and I may earn a commission if you purchase the book. This comes at no extra cost to you.

]]>
Problem #060 – realtor commissions https://mathspp.com/blog/problems/realtor-commissions 2022-06-12T16:47:18+02:00 2022-05-08T00:00:00+02:00

Two realtors discuss who's netting the award for highest average commission, but it isn't clear who the winner is...

# Problem statement

Alice and Bob are two realtors that work at the same premium real estate agency, WSH. Because WSH really wants to focus on selling premium properties, they instated a monetary prize that is awarded every two years to the realtor that has the highest average commission over the past two years.

The award for the years 2020 and 2021 is being attributed soon. One day, at the office, Alice overheard Bob gloating:

“I can't wait to get my money! I already know what I'll be doing with it!”

Alice turned to Bob and asked:

“How can you be so sure that you are the one netting the prize?”

Bob smirked and returned:

“I guess you haven't been paying attention, Alice! In 2020 I was the realtor with the highest average commission over that year... And in 2021 I did it again!”

Alice smiled and returned to work.

Who do you think is right? Is Bob definitely getting the award? Or is there a scenario in which Alice gets the prize?

# Solvers

Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:

• David H., Taiwan;
• Michael W., US;

Know how to solve this? Join the list of solvers by emailing me your solution!

# Solution

Bob is wrong because there is a scenario in which Alice can win the award... Even though Bob had the highest average commission both in 2020 and 2021. Does this seem counterintuitive? Because it is... This is an instance of the Simpson's Paradox.

To paint a clearer picture of how the Simpson's Paradox comes about, I will create a fairly extreme hypothetical scenario:

Suppose that Alice and Bob are the only realtors working for WSH, so that we don't have to care about anyone else.

Suppose that, in 2020, these were the commissions each one made:

• Bob sold a single house and made a $10,005 commission. • Alice sold a single house and made a$10,000 commission.

Furthermore, suppose that, in 2021, these were the commissions each one made:

• Bob sold a single house and made a $20,005 commission. • Alice sold 1000 houses and made a$20,000 commission on each one.

Here is a table summarising the average commission each one of them made for each year:

2020 2021
Alice \frac{1 \times 10000}{1} = 10000 \frac{1000 \times 20000}{1000} = 20000
Bob \frac{1 \times 10005}{1} = 10005 \frac{1 \times 20005}{1} = 20005

As we can see, Bob has a higher average commission in 2020... But also in 2021!

However, if we add a third column for 2020 and 2021 combined, everything becomes clear:

2020 2021 2020 + 2021
Alice \frac{1 \times 10000}{1} = 10000 \frac{1000 \times 20000}{1000} = 20000 \frac{1 \times 10000 + 1000 \times 20000}{1001} \approx 19990
Bob \frac{1 \times 10005}{1} = 10005 \frac{1...
]]>
Problem #059 – marching pegs https://mathspp.com/blog/problems/marching-pegs 2022-05-09T00:32:15+02:00 2022-04-17T00:00:00+02:00

How can you swap the coloured pegs if they can only march forward?

# Problem statement

Imagine seven round slots:

O O O O O O O

In the three left slots, you have Yellow pegs:

Y Y Y O O O O

In the three right slots, you have Green pegs:

Y Y Y O G G G

You have to swap the yellow pegs and the green ones, but of course there are some restrictions to what you can do:

• pegs can only move forward (that is, yellow pegs can only move to the right and green pegs can only move to the left); and
• pegs can only move:
• to the next (adjacent) slot if it is available;
• to the second next slot, if that means the peg “jumps over” a peg of another colour.

So, for example, in the configuration below, the green peg can move to the marked slot by jumping over a yellow peg:

G Y O
^   ^

As another example, in the situation below, no peg can move:

O G G Y Y O

With these restrictions, can you swap all pegs? That is, can you move the pegs so that all green pegs end up on the left and all yellow pegs end up on the right?

If you need any clarification whatsoever, feel free to ask in the comment section below.

This problem is based off of the puzzle you can see in the thumbnail picture, which you can play at Icon Park's Museum of Illusions.

# Solvers

Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:

• David H., Taiwan;
• Michael W., US;
• Zech Z., US;
• Michael H., US;
• Tanishk S., India;

Know how to solve this? Join the list of solvers by emailing me your solution!

# Solution

To solve this problem, my best suggestion is to go one move at a time, and to try and think ahead 2 or 3 moves each time you are about to do something. You don't need to look ahead too much to be able to tell if a move is a bad idea or not.

With that said, that can be easier for some and harder for others!

I will share one possible solution below. Each line represents the positions of the pegs after one single move. But first, let me show you a video shared on Twitter where one of you solved this problem with candy:

]]>
Problem #058 – identifying light bulbs https://mathspp.com/blog/problems/identifying-light-bulbs 2022-04-04T00:51:44+02:00 2022-03-28T23:00:00+02:00

# Problem statement

I have a very peculiar room in my house. It's a simple room that doesn't have much decoration. However, I do have 100 light bulbs hanging from the ceiling because I thought it would look cool. When I installed the 100 light bulbs I wanted maximum freedom, so I also installed 100 independent switches:

• each switch controls exactly one light bulb; and
• each light bulb is controlled by exactly one switch.

Of course I was completely silly, so I installed the switches in a room that is far from the room with the light bulbs and I completely forgot which light switch controls which light bulb. How can I identify which switch controls which light bulb in the least amount of trips possible?

For example, I could flip ON a switch and then go verify which light bulb turned ON, and I could do this for the 100 light bulbs... But that would take me 100 trips.

If you need any clarification whatsoever, feel free to ask in the comment section below.

# Solvers

Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:

• David H., Taiwan;
• Shubham S., India;
• Dan, USA;
• Jeena K., India;
• Frank X., Shenzhen, China;
• Wolfgang, Germany;
• Naveen K., India;
• Pedro G., Portugal;
• Dylan S., USA;
• Sean L., USA;

Know how to solve this? Join the list of solvers by emailing me your solution!

# Solution

I'll post the solution here once this problem has been live for 2 weeks, which will be around the 10th of April.

Don't forget to subscribe to the newsletter to get bi-weekly problems sent straight to your inbox.

]]>
Problem #057 – how to find the circle centre https://mathspp.com/blog/problems/how-to-find-the-circle-centre 2023-04-28T11:24:36+02:00 2022-03-13T00:00:00+01:00

Can you find the centre of the circle with just five lines?

# Problem statement

Suppose you have a circle, like the one in the figure below. At your disposal, you have a compass, a straightedge (like a ruler, but without length ticks), and a pencil.

Can you find the centre of the circle with just five lines? (Every time you use the compass counts as one line, and every time you use the straightedge counts as another line.)

If you need any clarification whatsoever, feel free to ask in the comment section below.

# Solvers

Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:

• Dmitry R., USA;
• Martin J., Czech Republic;
• David H., Taiwan;
• Paul M., USA;
• Luis C., Peru;
• Pietro P., Italy;

Know how to solve this? Join the list of solvers by emailing me your solution!

# Solution

There are many ways in which the centre of the circle can be found! However, doing that with just 5 lines is the challenge.

## Deductive reasoning

Recall that the centre of the circle is the point that is at the same distance of all the points in the circumference. So, if you draw any chord and then draw its bisector, you know that bisector will go through the centre of the circle (point A in the figure):

In the figure above, I picked two arbitrary points D and E and drew the chord [DE]. Then, I used D and E two draw to circles:

• one centred at D with radius equal to the length of [DE]; and
• another centred at E with radius equal to the length of [DE].

Then, the line defined by the two intersections of those two circles goes through the centre (A). If we do that once more, the intersections of those two bisectors give you the centre:

However, this uses a total of 8 lines. We want to do this in just 5... And yet, going down to 6 lines is easy: we just need to realise we don't really care about the chords, only their endpoints... And picking arbitrary points on the circumference doesn't cost any “lines”: 4 circles and 2 lines make up a total of 6 lines.

The final step comes from realising that we don't need 4 separate circles! The two bisector lines of the implied chords can be drawn with just 3 circles if we pick the points well enough!

After drawing the first two auxiliary circles, pick one of the circles. That circle will intersect the original circle at a point that you haven't used yet (H in the figure below). Use that point as the centre of the third circle, which you can draw with a radius equal to the other two auxiliary circles:...

]]>
Problem #056 – tennis tournament https://mathspp.com/blog/problems/tennis-tournament 2022-03-08T14:19:33+01:00 2022-02-20T00:00:00+01:00

How many matches does it take to find the winner of a tennis tournament?

# Problem statement

Suppose that $$n$$ players are going to play in a tennis tournament. The players will be randomly assigned to brackets, and each bracket plays a match. The winner of each match advances to the next bracket, until the two final players face each other in the final match, which determines the winner.

As a function of the number of players $$n$$, how many matches are needed to determine the winner of the tournament?

If you need any clarification whatsoever, feel free to ask in the comment section below.

# Solvers

Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:

• David H., Taiwan;
• Umberto M., Italy;
• Christ van W., The Netherlands;
• Thierry Z., Burkina Faso;
• Kishan M., India;
• Ioan E., Ukraine;
• Soliu, Nigeria;
• Francisco M., Mexico;
• Han A., Malaysia;
• Pavan J., India;
• David F., United States;

Know how to solve this? Join the list of solvers by emailing me your solution!

# Solution

There is a nice intuitive solution to this problem that means you don't need to do any calculations whatsoever!

Each time two players face each other, one player leaves the tournament and the other player remains. On top of that, determining the winner is the same as saying that all players have left the tournament, except for one. Thus, if there are $$n$$ players, we want to eliminate a total of $$n - 1$$ players, which means we need to play $$n - 1$$ matches.

Don't forget to subscribe to the newsletter to get bi-weekly problems sent straight to your inbox.

]]>
Problem #055 – horse racing https://mathspp.com/blog/problems/horse-racing 2023-04-12T11:13:18+02:00 2022-02-06T22:00:00+01:00

25 horses racing, and you have to find out the fastest ones!

# Problem statement

You are in a horse racing track, and you have 25 mechanical horses in front of you. They are programmed to race around the track in a pre-programmed time that is always the same, even though you have no idea what these times are.

The racing track accommodates up to 5 horses at a time, and after the race, it gives you the relative rankings of the horses: it tells you which horse came in 1st, 2nd, 3rd, 4th, and 5th, but it doesn't tell you the times.

What is the minimum number of races you need to figure out what are the top 3 fastest horses?

If you need any clarification whatsoever, feel free to ask in the comment section below.

# Solvers

Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:

• David H., Taiwan;
• Luiz G., UK;
• Ashok C., India;
• Pedro G., Portugal;

Know how to solve this? Join the list of solvers by emailing me your solution!

# Solution

There is a way to find the fastest three horses with seven races only. To show that 7 is the minimum number of races needed, we need to do two things:

• we need to show that there is a way to arrange the seven races in such a way that we find the three fastest horses; and
• we need to prove it is impossible to solve this in six races or less.

Typically, finding a solution in seven races is easier to do than to show it is impossible to find a solution with six races or less, so we will start with the easier thing and show how seven races work.

## Seven races works

Here is how you can find the three fastest horses with only seven races.

The first thing you do is split the 25 horses in five groups of five, let's call them the groups $$A$$ through $$E$$. Then, you race each of the groups, which means that now you know what is the fastest horse of each group, the second fastest horse of each group, etc. Let's use the values $$1$$ through $$5$$ to talk about the (ranked) horses of each group.

So, $$A1$$ is the fastest horse of group $$A$$ and $$C4$$ is the fourth fastest horse of group $$C$$.

After determining the fastest horse of each group, you bring them together and race them. In other words, you race the horses $$A1$$, $$B1$$, $$C1$$, $$D1$$, and $$E1$$. This is the sixth race. Suppose these are the results:

• 1st place: $$A1$$;
• 2nd place: $$B1$$;
• 3rd place: $$C1$$;
• 4th place: $$D1$$;
• 5th place: $$E1$$;
]]>
Problem #054 – imperfect compression https://mathspp.com/blog/problems/imperfect-compression 2022-02-07T00:33:55+01:00 2022-01-23T00:00:00+01:00

Can you show that perfect compression is impossible?

# Problem statement

Compression is great: it is what lets you take that giant folder you have and reduce its size to save some memory on your laptop. Of course, you only do these compressions happily because you know you don't lose information when you compress things. The data is just... compressed!

For compression to be useful, it has to be bidirectional: you must be able to recover the original data from the compressed version. This is only possible if two different pieces of data never get compressed into the same thing. (In mathematical terms, we say that the compression must be injective.)

Now, on top of that, we are interested in compression that actually works, right? That is, in compression that reduces the size of things. Right?

Right! Now, the challenge is for you to show that no compression mechanism is perfect. In other words, show that if a compression mechanism is bidirectional and it manages to take some pieces of data and transform them into something smaller, then, there are pieces of data that will become larger by the action of the compression mechanism.

If it makes it easier for you, we can suppose that the data we are talking about are just sequences of letters. So, we are talking about compression mechanisms that take sequences of letters and try to build smaller sequences of letters, the compression. For example, maybe the sequence aaaaaa gets compressed into Aaab, but maybe the mechanism fails on AAAAAA because it “compresses” it into arghfewtoen.

If you need any clarification whatsoever, feel free to ask in the comment section below.

# Solvers

Congratulations to the ones that solved this problem correctly and, in particular, to the ones who sent me their correct solutions:

• David H., Taiwan;

Know how to solve this? Join the list of solvers by emailing me your solution!

# Solution

Let's assume that there is a perfect compression algorithm. For the empty sequence, what does this algorithm do? It has to compress the empty sequence into the empty sequence, because there is no shorter sequence to compress the sequence into.

Now, let's think about sequences of length 1. None of those can be compressed into the only sequence of length 0, because there is already a sequence compressed into that (itself). Thus, all sequences of length 1 must map to other sequences of length 1. Of course they don't map to sequences of length 2 or greater, otherwise the compression would actually make the sequences larger.

Therefore, the sequences of length 1 all map to each other, and no two sequences can map to the same one, so the compression algorithm really only works as a shuffling of the sequences...

Now, we can just repeat this train of thought indefinitely: for the sequences of length 2, none of them can map to sequences of length 0 or 1, because those are all...

]]>