FEATURED

A Broken Circle

There are N points on a circle. If we draw all the chords connecting these points and no three of them intersect at the same point, in how many parts will the interior of the circle get broken?

For example, when N is equal to 1, 2, 3, 4, and 5, we get 1, 2, 4, 8, and 16 parts respectively.

The answer, somewhat surprisingly, is not 2ᴺ⁻¹, but 1 + N(N-1)/2 + N(N-1)(N-2)(N-3)/24.

In order to see that, we start with a single sector, the interior of the circle, and keep successively drawing chords. Every time we draw a new chord, we increase the number of parts by 1 and then add 1 extra part for each intersection with previously drawn chords.

Therefore, the total number of parts at the end will be:

1 + the number of the chords + the number of the intersections of the chords

Each chord is determined by its 2 endpoints and therefore the number of chords is N(N-1)/2.

Each intersection is determined by the 4 endpoints of the two intersecting chords and therefore the number of intersections is N(N-1)(N-2)(N-3)/4!.

A Short, Brutal Riddle

Left alone, I’m a word with five letters.
I’m honest and fair, I’ll admit.
Rearranged, I’m of no use to trains.
Again, and I’m an overt place, warm and well lit.

What am I?

The answer is LIAR. After rearranging the letters, you can get RAIL – important for trains, or LAIR – a dark, hidden place. Since the riddler is a liar, the resulting words are exactly the opposite of his descriptions.

Source:

Puzzling StackExchange

FEATURED

Sum Up to 15

Tango and Cash are playing the following game: Each of them chooses a number between 1 and 9 without replacement. The first one to get 3 numbers that sum up to 15 wins. Does any of them have a winning strategy?

Place the numbers from 1 to 9 in a 3×3 grid so that they form a magic square. Now the game comes down to a standard TIC-TAC-TOE, and it is well-known that it always leads to a draw when both players use optimal strategies.

FEATURED

David Copperfield

David Copperfield and his assistant perform the following magic trick. The assistant offers a person from the audience to pick 5 arbitrary cards from a regular deck and then hands them back to him. After the assistant sees the cards, he returns one of them to the audience member and gives the rest one by one to David Copperfield. After the magician receives the fourth card, he correctly guesses what card the audience member holds in his hand. How did they perform the trick?

Out of the five cards, there will be (at least) two of the same suit; assume they are clubs. Now imagine all clubs are arranged in a circle in a cyclic manner – A, 2, 3, … J, Q, K (clock-wise), and locate the two chosen ones on it. There are two arks on the circle which are connecting them and exactly one of them will contain X cards, with X between 0 and 5. Now the assistant will pass to David Copperfield first the clubs card which is located on the left end of this ark, will return to the audience member the clubs card which is located on the right end of it and, with the remaining three cards, will encode the number X. In order to do this, he will arrange the three extra cards in increasing order – first clubs A-K, then diamonds A-K, then hearts A-K and finally spades A-K. Let us call the smallest card in this order “1”, the middle one “2” and the largest one “3”. Now, depending on the value of X, the assistant will pass the cards “1”, “2” and “3” in the following order:

X=0 ⇾ 1, 2, 3
X=1 ⇾ 1, 3, 2
X=2 ⇾ 2, 1, 3
X=3 ⇾ 2, 3, 1
X=4 ⇾ 3, 1, 2
X=5 ⇾ 3, 2, 1

In this way David Copperfield will know the suit of the audience member’s card and also with what number he should increase the card he received first in order to get value as well. Therefore, he will be able to guess correctly.

Touching Pencils

Can you arrange 6 new identical pencils in space such that every two of them touch each other? What if you have 7 pencils?

Remark: The construction doesn’t need to be stable.

Below you can see solutions for 6 and 7 pencils. The construction with 6 pencils is stable, the construction with 7 pencils – not.

Gods of Truth

You encounter three Gods in a room – the God of Truth, the God of Lie and the God of Uncertainty. You don’t know which one is which, but know that the God of Truth always says the truth, the God of Lie always says the lie and the God of Uncertainty sometimes lies and sometimes says the truth. You can ask in succession each of the Gods a unique question, to which they can reply only with “Yes” or “No”. However, their responses will be in their native language – “Da” or “Ne”, and you don’t know which translation to which answer corresponds. Your task is to figure out what questions to ask the Gods, so that will recognize which one of them is the God of Truth, which one is the God of Lie and which one is the God of Uncertainty.

Label the gods with numbers – 1, 2, and 3.

First, ask god 1 “If I ask you whether god 2 is random, would you say ‘Da’?”. If he responds “Da”, then god 3 is not the god of uncertainty. If he responds “Ne”, then god 2 is not the god of uncertainty. In both cases we will be able to find a god which is not the god of uncertainty, let without of generality that is god 3.

Next, ask god 3 “If I ask you whether you are the God of Lie, would you say ‘Da’?”. If he says “Da”, then he is the God of Truth. If he says “No”, then he is the God of Lie.

Finally, ask god 3 whether god 1 is the God of Uncertainty and conclude the identities of all gods.

Black and White

A boy draws 2015 unit squares on a piece of paper, all oriented the same way, possibly overlapping each other. Then the colors the resulting picture in black and white chess-wise, such that any area belonging to an even number of squares is painted white and any area belonging to an odd number of squares is painted black.

Prove that the total black area is at least one.

Draw a grid in the plane which is parallel to the sides of the squares. Then, take the content of each cell of the grid and translate it (move it) to some chosen unit square. The points in that unit square which are covered by odd number of black pieces color in black, the rest color in white. It is easy to see that after doing this, the entire unit square will be colored in black (each of the 2015 squares cover it once completely). This implies that the total black area is no less than 1.

In the Padurea Forest

In the Padurea forest there are 100 rest stops. There are 1000 trails, each connecting a pair of rest stops. Each trail has some particular level of difficulty with no two trails having the same difficulty. An intrepid hiker, Sendeirismo has decided to spend a vacation by taking a hike consisting of 20 trails of ever increasing difficulty. 
Can he be sure that it can be done?

He is free to choose the starting rest stop and the 20 trails from a sequence where the start of one trail is the end of a previous one.

Place one hiker in each of the rest stops. Now, go through the trails in the forest one by one, in increasing difficulty, and every time you pick a trail, let the two hikers in its ends change places. This way the 100 hikers would traverse 2000 trails in total, and therefore one of them would traverse at least 20 trails.

FEATURED

Prisoners and Boxes

There are 100 inmates living in solitary cells in a prison. In a room inside the prison there are 100 boxes and in each box there is a paper with some prisoner’s name (all different). One day the warden tells the prisoners that he has aligned next to the wall in a special room 100 closed boxes, each of them containing some prisoner’s name (all different). He will let every prisoner go to the room, open 50 of the boxes, then close them and leave the room the way it was, without communicating with anybody. If all prisoners find their names in the boxes they open, they will be set free, otherwise they will be executed. The prisoners are allowed to come up with a quick plan before the challenge begins. Can you find a strategy which will ensure a success rate of more than 30%?

The prisoners can assign numbers to their names – 1, 2, 3, … , 100. When prisoner X enters the room, he should open first the X-th box in the line. If he sees inside prisoner’s Y name, he should open next the Y-th box in the line. If he sees in it prisoner’s Z name, he should open next the Z-th box in the line and so on.

The only way which will prevent all prisoners from finding their names is if there is a long cycle of boxes (length 51 or more), such that the first box in the cycle directs to the second box in it, the second box to the third box, the third box to the fourth box and so on.

It is not hard to compute that the probability of having a cycle of length K>50 is exactly 1/K. Then the probability for failure will be equal to the sum 1/51 + 1/52 + … + 1/100, which is very close to ln(100) – ln(50) = ln(2) ~ 69%. Therefore, this strategy ensures a success rate of more than 30%.

Trips in Bulmenia

In the country of Bulmenia there are 40 big cities. Each of them is connected with 4 other big cities via paths, and you can get from any city to any other via these paths.

  1. Show that you can create a trip passing through every path exactly once that ends in the city it starts from.
  2. Show that you can create one or multiple trips, such that every trip passes through different cities, ends in the city it starts from, and also every city is part of exactly one trip.

Remark: The paths can intersect each other, but you cannot switch from one path to another midway.

  1. Let us call a trip that ends in the city it starts from a “loop”. Start from any city and keep traveling without using any path twice. If at some point you can’t continue, stop, creating a loop, and modify your trip as follows. Pick any city you have visited from which there are unused paths going out, and once again start traveling along the unused paths until you can’t continue further. Add the newly formed loop to the original trip and continue this procedure until there are no unused paths left, thus completing a loop passing through every path exactly once. This method works because there is an even number of paths going out from every city and you can get from any city to any other.
  2. Use the loop from 1. and color every second path on it in black. Then, notice that there are 2 black paths going out from evey city. Therefore, these black paths create one or multiple disjoint loops passing through every city in Bulmenia exactly once.
Source:

IMO 2020