5th ASU 1965

5th ASU 1965 problems


1. (a) Each of x₁, ... , x_n is -1, 0 or 1. What is the minimal possible value of the sum of all x_ix_j with 1 ≤ i < j ≤ n? (b) Is the answer the same if the x_i are real numbers satisfying 0 ≤ \|x_i\| ≤ 1 for 1 ≤ i ≤ n?
2. Two players have a 3 x 3 board. 9 cards, each with a different number, are placed face up in front of the players. Each player in turn takes a card and places it on the board until all the cards have been played. The first player wins if the sum of the numbers in the first and third rows is greater than the sum in the first and third columns, loses if it is less, and draws if the sums are equal. Which player wins and what is the winning strategy?
3. A circle is circumscribed about the triangle ABC. X is the midpoint of the arc BC (on the opposite side of BC to A), Y is the midpoint of the arc AC, and Z is the midpoint of the arc AB. YZ meets AB at D and YX meets BC at E. Prove that DE is parallel to AC and that DE passes through the center of the inscribed circle of ABC.
4. Bus numbers have 6 digits, and leading zeros are allowed. A number is considered lucky if the sum of the first three digits equals the sum of the last three digits. Prove that the sum of all lucky numbers is divisible by 13.
5. The beam of a lighthouse on a small rock penetrates to a fixed distance d. As the beam rotates the extremity of the beam moves with velocity v. Prove that a ship with speed at most v/8 cannot reach the rock without being illuminated.
6. A group of 100 people is formed to patrol the local streets. Every evening 3 people are on duty. Prove that you cannot arrange for every pair to meet just once on duty.
7. A tangent to the inscribed circle of a triangle drawn parallel to one of the sides meets the other two sides at X and Y. What is the maximum length XY, if the triangle has perimeter p?
8. The n² numbers x_ij satisfy the n³ equations: x_ij + x_jk + x_ki = 0. Prove that we can find numbers a₁, ... , a_n such that x_ij = a_i - a_j.
9. Can 1965 points be arranged inside a square with side 15 so that any rectangle of unit area placed inside the square with sides parallel to its sides must contain at least one of the points?
10. Given n real numbers a₁, a₂, ... , a_n, prove that you can find n integers b₁, b₂, ... , b_n, such that the sum of any subset of the original numbers differs from the sum of the corresponding b_i by at most (n + 1)/4.
11. A tourist arrives in Moscow by train and wanders randomly through the streets on foot. After supper he decides to return to the station along sections of street that he has traversed an odd number of times. Prove that this is always possible. [In other words, given a path over a graph from A to B, find a path from B to A consisting of edges that are used an odd number of times in the first path.]
12. (a) A committee has met 40 times, with 10 members at every meeting. No two people have met more than once at committee meetings. Prove that there are more than 60 people on the committee. (b) Prove that you cannot make more than 30 subcommittees of 5 members from a committee of 25 members with no two subcommittees having more than one common member.
13. Given two relatively prime natural numbers r and s, call an integer good if it can be represented as mr + ns with m, n non-negative integers and bad otherwise. Prove that we can find an integer c, such that just one of k, c - k is good for any k. How many bad numbers are there?
14. A spy-plane circles point A at a distance 10 km with speed 1000 km/h. A missile is fired towards the plane from A at the same speed and moves so that it is always on the line between A and the plane. How long does it take to hit?
15. Prove that the sum of the lengths of the edges of a polyhedron is at least 3 times the greatest distance between two points of the polyhedron.
16. An alien moves on the surface of a planet with speed not exceeding u. A spaceship searches for the alien with speed v. Prove the spaceship can always find the alien if v>10u.