Mathematics 7 - Puzzle Prime

Vectors -1, 0, 1

Section: Brain Teasers Category: Mathematics

Difficulty: Expert

Consider all 1024 vectors in a 10-dimensional space with elements ±1. Show that if you change some of the elements of some of the vectors to 0, you can still choose a few vectors, such that their sum is equal to the 0-vector.

SOLUTION

Denote the 1024 vectors with u_i and their transformations with f(u_i). Create a graph with 1024 nodes, labeled with u_i. Then, for every node u_i, create a directed edge from u_i to u_i-2f(u_i). This is a valid construction, since the vector u_i-2f(u_i) has elements -1, 0, and 1 only. In the resulting graph, there is a cycle:

v₁ ⇾ v₂ ⇾ … ⇾ v_k ⇾ v₁.

Now, if we pick the (transformed) vectors from this cycle, their sum is the 0-vector:

f(v₁) + f(v₂) + … + f(v_k) = (v₂ – v₁)/2 + (v₃ – v₂)/2 + … + (v₁ – v_k)/2 = 0.

Unknown Author January 18, 2021

0 Comments

Odd Rectangle

Section: Brain Teasers Category: Mathematics

Difficulty: Expert

The sides of a rectangle have lengths which are odd numbers. The rectangle is split into smaller rectangles with sides which have integer lengths. Show that there is a small rectangle, such that all distances between its sides and the sides of the large rectangle have the same parity, i.e. they are all even or they are all odd.

SOLUTION

Split the large rectangle into small 1×1 squares and color it in black and white, chessboard-style, such that the four corner squares are black. Since the large rectangle has more black squares than white squares, one of the smaller rectangles also must have more black squares than white squares. Therefore, the four corners of that smaller rectangle are all black. Then, it is easy to see that all distances between its sides and the sides of the large rectangle have the same parity.

Source:

Shortlist IMO 2017

Unknown Author January 6, 2021

0 Comments

Diagonal in a Rectangle

Section: Brain Teasers Category: Mathematics

Difficulty: Advanced

A 1000 × 1004 rectangle is split into 1 × 1 squares. How many of these squares does the main diagonal of the large rectangle pass through?

SOLUTION

Notice that the number of small squares the main diagonal passes through is equal to the number of horizontal and vertical lines it intersects. Indeed, every time the diagonal goes through the interior of one square to the interior of another, it must intersect one of these lines.

There are 1000 + 1004 = 2004 lines which are intersected by the main diagonal. However, on four occasions (which is the greatest common divisor of 1000 and 1004), the main diagonal intersects one horizontal and one vertical line at the same time, which results in double-counting., so we must subtract 4 from the answer.

Therefore, the answer is 1000 + 1004 – 4 = 2000.

Unknown Author December 18, 2020

0 Comments

Blue and Red Points

Section: Brain Teasers Category: Mathematics

Difficulty: Advanced

You have 100 blue and 100 red points in the plane, no three of which lie on one line. Prove that you can connect all points in pairs of different colors so that no two segments intersect each other.

SOLUTION

Connect the points in pairs of different colors so that the total length of all segments is minimal. If any two segments intersect, you can swap the two pairs among these four points and get a smaller total length.

Unknown Author December 6, 2020

0 Comments

Close the Loop

Section: Brain Teasers Category: Mathematics

Difficulty: Hard

Alex and Bob are playing a game. They are taking turns drawing arrows over the segments of an infinite grid. Alex wins if he manages to create a closed loop, Bob wins if Alex does not win within the first 1000 moves. Who has a winning strategy if:

a) Alex starts first (easy)
b) Bob starts first (hard)

Remark: The loop can include arrows drawn both by Alex and Bob.

SOLUTION

In both cases, Bob wins. An easy strategy for part a) is the following:

Every time Alex draws an arrow, Bob draws an arrow in such a way that the two arrows form an L-shaped piece and either point towards or away from each other. Since every closed loop must contain a bottom left corner, Alex cannot win.

For part b), Bob should use a modification of his strategy in part a). First, he draws a horizontal arrow. Then, he splits the remaining edges into pairs, as shown in the image below. If Alex draws one arrow on the grid, then Bob draws its paired arrow, such that the two arrows point either towards or away from each other. The only places where a loop can have a bottom left corner are where Bob drew the first arrow or the grid points directly above it. However, if a loop has a bottom left corner there, then it is easy to see that it must have at least one more bottom left corner elsewhere, which is impossible.

Unknown Author October 12, 2020

0 Comments

One to One Hundred

Section: Brain Teasers Category: Mathematics

Difficulty: Advanced Tags: Algorithm

99 unique numbers between 1 and 100 are listed one by one, with 5 seconds pause between every two consecutive numbers. If you are not allowed to take any notes, what is the best way to figure out which is the missing number?

SOLUTION

Keep up adding the given numbers and remember only the last two digits of the sum. In the end, if the result is less than 50, subtract it from 50. If the result is larger than 50, subtract it from 150. This method works because the sum of all numbers from 1 to 100 is 5050, so if you know the sum of all the listed numbers, you will know the missing number as well.

Unknown Author September 6, 2020

0 Comments

Handshakes at a Party

Section: Brain Teasers Category: Mathematics

Difficulty: Medium Tags: Graph Theory

100 guests go to a party and some of them shake hands with each other. Show that there are two guests who handshake the same number of people.

SOLUTION

Each of the people at the party has shaken hands between 0 and 99 times. However, if someone has shaken hands 0 times (with nobody), it is impossible that another one has shaken hands 99 times (with everybody). Therefore there are at most 98 different options for the number of handshakes at the party, and thus two of the guests have shaken hands the same number of times.

Unknown Author August 27, 2020

0 Comments

A Beetle and Four Spiders

Section: Brain Teasers Category: Mathematics

Difficulty: Advanced

A beetle is located in the center of a square carpet. The edges of the carpet are colored in red, green, blue, and yellow. Four spiders of the same colors are on the carpet’s corners. Each spider can only move on the edge with its matching color. Can the beetle escape the carpet and flee without encountering the spiders if it is 1.5 times slower than them?

SOLUTION

No, the spiders will always be able to contain the beetle within the carpet. We draw two perpendicular lines passing through the beetle which are parallel to the diagonals of the square. The spiders’ strategy is to follow the four points where these lines intersect with the boundary of the square. When a spider’s corresponding intersection point moves to an edge of a different color, the spider waits in the corner. In order to accomplish this strategy, the speeds of the spiders need to be at least √2~1.4 times higher than the speed of the beetle.

Unknown Author August 1, 2020

0 Comments

The Twelve Matchsticks

Section: Brain Teasers Category: Mathematics

Difficulty: Hard Tags: Matchsticks

With 12 matches you can easily create a shape with area 9 and a shape with area 5, as shown on the picture below. Can you rearrange the 12 matchsticks, so that they encompass an area of 4?

Remark: You should have only one resulting shape and no matches should be unused.

SOLUTION

First, create a Pythagorean triangle with sides 3, 4, 5, and area 6. Then simply flip its right angle inwards, so that the area decreases by 2.

Martin Gardner July 18, 2020

0 Comments

Programmers and Coins

Section: Brain Teasers Category: Mathematics

Difficulty: Advanced

One programmer draws on a sheet of paper several circles in a line, representing coins, and puts his thumb on the first circle, covering the rest with his hand. Then he asks another programmer to guess how many different head-tail combinations are possible if someone flips all the (imaginary) coins on the paper. The second programmer, without knowing the number of circles, takes the pen and writes down a number. Then the first programmer lifts his hand and sees that the correct answer is written on the paper. How did the second programmer manage to do this?

SOLUTION

The second programmer wrote down “1” in front of the first circle. When the second programmer lifted his hand, he saw the number “10…00”, which is exactly the number of possible head-tail combinations in binary system.

Unknown Author July 6, 2020

0 Comments