In a parliament, there are 100 people, and some of these people are enemies with each other. Show that you can split the people into 2 groups so that each person has at least as many enemies in the opposite group as he has in his own.
SOLUTION
For each split of the people into 2 groups, compute the animosity level of each person by subtracting the number of enemies in the opposite group from the number of enemies in his own group. Then, split the people into 2 groups so that the total animosity level of all of them is as little as possible. If there is a person, who has more enemies in his own group than the opposite one, then by transferring him to the other group, we will reduce the total animosity level of the people and will get a contradiction.
You place two stones on a chessboard and start moving them one by one, every time shifting a stone to an adjacent cell – left, right, up, or down, without letting the stones at any time occupy the same cell. Is it possible to find such a sequence of moves, that all possible combinations for the position of the stones occur exactly once?
SOLUTION
No, such sequence does not exist. Call a position of the stones “matching” if the stones occupy cells of the same color, and “opposite” if the stones occupy cells of opposite colors. If such sequence exists, then the number of matching and opposite positions must differ by at most 1. However, the number of matching positions is 64×31, whereas the number of opposite positions is 64×32, so this is not true.
You had 10kg of cucumbers, each of which consisted of 99% water. After leaving them in the sun, some of the water in the cucumbers evaporated. If the cucumbers ended up with 98% water in them, how much of their weight did they lose?
SOLUTION
The cucumbers lost half of their weight.
If the water was 99% of the total weight, the remaining substance must have weighed 0.1kg. If after the evaporation the substance comprises 2% = 1/50 of the cucumbers, the total weight must be 50 x 0.1kg = 5kg.
On the picture, you can see an example of a wall made of 2×1 bricks. On the wall, there are 2 cracks, which are straight lines passing through the whole wall from top to bottom and from left to right, without intersecting any bricks.
Can you make the following walls without any cracks:
wall 5×6 with 15 bricks;
wall 6×6 with 18 bricks?
SOLUTION
The solution for a 5×6 wall is shown below. However, if the wall has dimensions 6×6, it is impossible to build it without any cracks. Indeed, assume the wall does not have any cracks. Therefore every line passing through it must intersect 2, 4, or 6 bricks. Since there are in total 10 lines passing through the wall and each brick is intersected by exactly one of them, the total number of bricks must be at least 10 x 2 = 20 > 18. This yields a contradiction.
A large rectangle is partitioned into smaller rectangles, each of which has integer length or integer width. Prove that the large rectangle also has integer length or integer width.
SOLUTION
This problem can be solved using graph theory, but the most elegant solution is based on some basic calculus.
Place the big rectangle in the plane so that its sides are parallel to the X and Y axes. Now integrate the function f(x)=sin(πx)sin(πy) over the boundary of any small rectangle. Since at least one of its sides has integer length, the result will be 0. If you sum all integrals taken over the boundaries of the small rectangles and cancel the opposite terms, you will get that the integral of f(x) over the boundary of the large rectangle is also equal to 0. Therefore at least one of its sides has integer length.
You need to cross a river, from the north shore to the south shore, via a series of 13 bridges and six islands, which you can see in the diagram below. However, as you approach the water, a hurricane passes and destroys some (possibly none/all) of the bridges. If the probability that each bridge gets destroyed is 50%, independently of the others, what is the chance that you will be able to cross the river after all?
SOLUTION
Imagine there is a captain on a ship, who wants to sail through the river from West to East. You can see that he will be able to do this if and only if you are not able to cross the river. However, if you rotate the diagram by 90 degrees, you can also see that the probability that you cross North-South is equal to the probability that he sails West-East, and therefore both probabilities are equal to 50%.
Consider an arbitrary acute triangle ABC. Let E be the intersection of the bisector at vertex C and the bisection of the side AB. Let F and G be the projections of E on AC and BC respectively.
Since E belongs to the bisection of AB, we must have AE = BE. Also, since E belongs to the bisector of C, we must have EF = EG. However, this would imply that triangles AEF and BGF are identical, and then AF = BF. We also have that CF = CG, which implies that AC = BC. The arbitrarily chosen triangle ABC is isosceles!
Can you find where the logic fails?
SOLUTION
The bisector of C and the bisection of AB always intersect outside the triangle, on the circumcircle. One of the points F and G always lies on the segment AC or BC, and the other one does not.
Suppose you have 10 people with different heights in one row. Show that you can always remove 6 of them, so that the remaining 4 are arranged with respect to their heights (either increasing or decreasing).
SOLUTION
Mark the first person with number 1. Look for the next person after him, who is taller, and also mark him with number 1. Then look for the first person after the second one, who is taller, and also mark him with number 1. If you find a fourth one, then you already got the four people you are looking for.
If not, mark the first unmarked person with number 2. Look for the next unmarked person after him, who is taller, and also mark him with number 2. Continue with the procedure, until you either find 4 people in the line, whose heights are increasing, or have people who are marked with numbers 1, 2, 3 and 4.
Now pick a person, who is marked with number 4. Then look for the closest person on the left, who is marked with number 3, pick him up. He will be taller, because otherwise the first person would have been labeled 3 as well. Similarly, look for the closest person, marked with 2, on the left of the last one, pick him up. Repeat this once again and you will find 4 people in the line, whose heights are decreasing.
Every second, a new zombie drops down on one of the 9 spots of your lawn, which is currently unoccupied. All zombies move towards your house on the left with constant speed, and each of them needs exactly 1 second to traverse a spot of the lawn. Once a zombie steps out of the lawn, it enters your house and waits there for the others (thus each zombie travels total distance between 1 and 9 spots).
Show that after some time, the total distance traversed by any 1000 consecutive zombies will be within the range of just 50 spots.
Remark: Assume your house can accommodate an unlimited amount of zombies.
SOLUTION
Since the number of zombies on the lawn never decreases, it must stabilize at some point. Therefore after some time T, there will be exactly K zombies on the lawn at all times, 1 ≤ K ≤ 9.
Consider any 1000 consecutive zombies appearing past time T and take a picture of the lawn at the moment each of them gets dropped on it – this makes a total of 1000 pictures. Since on every picture, there are exactly K zombies, we see exactly 1000K zombies on these pictures.
Now notice that almost all of the selected 1000 zombies appear on as many pictures as lawn spots they traverse. The zombies for which this is not true are just the K zombies, which appear on the last picture. We easily see that they have traveled between 1 + 2 + … + K − 1 and (10 − K) + (11 − K) + … + 8 spots more than the number of pictures they appear on.
Similarly, on the 1000 pictures we have taken, there are K−1 additional zombies, which appear multiple times (you can see all of them on the first picture). The total number of times they show up is again between 1 + 2 + … + K − 1 and (10 − K) + (11 − K) + … + 8.
Therefore we conclude that the total distance the selected 1000 zombies travel is equal to 1000K ± {[(10 − K) + (11 − K) + … + 8] − [1 + 2 + … + K − 1]} = 1000K ± (9 − K)(K − 1).Since (9 − K)(K − 1) is a number between 0 and 16, this solves the problem.
Prove that you can not cover the plane with infinite strips which have a total sum of their widths equal to 1.
SOLUTION
Take a circle with radius 1 in the plane. A strip with width X covers at most an area of 2X of the circle. Therefore all strips cover at most an area of 2, which is smaller than the total area of the circle (~3.14).
Please note:
This action will also remove this member from your connections and send a report to the site admin.
Please allow a few minutes for this process to complete.
