Monday, August 31, 2009

What's KBB?

That's the question I got asked a lot lately. In short, KBB was a series of competitions that I wrote for the Olimpiade forum. The participants were all Indonesian Olympiad trainees, and they are surprisingly good. Sometimes they found solutions that are completely different from mine but just as original if not more, and I will post their solutions here as well.

  • There have been 3 KBBs total, and I'm planning to write all the problems and solutions here for archival purposes. I started with KBB2 because I somehow lost the problems to KBB1. When I do find them, I will surely post them here.

  • Each KBB consists of 10 problems, 2 from each field. They are ordered in ascending difficulty (1 = easiest, 10 = hardest). Of course, difficulty itself is a very elusive and relative term, so I must say that they are ordered in estimated difficulty. As such, problem 1 to 5 consist of 1 problem of each field, and so do problem 6 to 10. You can think problem 1 to 5 as the "warm up" problems and problem 6 to 10 as the real interesting ones.

  • I can say that I wrote all of these problems. Again, writer of a problem is sometimes a very controversial subject. Let's just say I get the inspirations for these problems somewhere else but the final version themselves (including the numbers) are all mine.

Wednesday, August 26, 2009

KBB2 Problem 10

Let $P$ be a permutation of the number $(1,2,\cdots,n)$. We apply a process as follows:

Start with the leftmost number and move to the right. Everytime we encounter a number that's bigger than the leftmost number, we swap that number and the leftmost number. Continue until we arrive at the rightmost number.

Define the rank of $P$ as the number of swaps that happened. For example, the permutation$(2,3,1,4)$ has rank 2 because:

$\displaystyle (2,3,1,4) \to (3,2,1,4) \to (4,2,1,3)$

Let$S_n$ be the sum of the ranks of all possible permutations of $(1,2,\cdots,n)$. Is there an $n$ for which$S_n > 2009n!$?

Wednesday, August 19, 2009

KBB2 Problem 9

Find the maximum $k$ such that

$\displaystyle (a^4 + b^4+c^4+d^4) + 4kabcd \geq \frac{k+1}{4}(a^2+b^2+c^2+d^2)^2$

always holds for $a,b,c,d$ positive reals.

Monday, August 17, 2009

Eye Color Riddle

I got this problem during our most recent hiking trip. It served as a fun distraction and a way to kill time during our downhill hike. I will post the solution in about a week's time. Please feel free to post yours in the comment. The riddle credit goes to Vallent Lee.

On an isolated island there are 50 people with blue eyes, 50 people with brown eyes, and an oracle with green eyes. Every day at noon, a ship comes to the island. Anyone who can correctly mention his or her eye color can board the ship and leave.

One day, the oracle says "there is at least one person with blue eyes."

Who leaves the island and when?

KBB2 Problem 8

We are given a circle centered on $O$ with radius $r$, and given lengths $a,b$ with $a > b$. We are also given a point $P$ on the circle.

For any point $B$ on the circle, construct a point $A$ such that $AP = a, BP = b$. Also construct rhombus $ABCD$ such that $D,B,P$ lie on the same line.

Suppose $B$ moves around the circle and we repeat the construction process above, as long as there is a point $A$ that satisfies the conditions. Show that as $B$ moves around the circle, the resulting point $D$ will trace a straight line. Determine the angle formed by that line and $PO$.

KBB2 Problem 7

Prove that for any $n > 1$, the polynomial

$P(x) = 2008x^n + 7x + 56$

cannot be factored into two non-trivial integer polynomials.

(A polynomial is non-trivial if its highest degree is greater than one)

KBB2 Problem 6

An integer is called homogenous if its decimal representation consists of 1 number. For example, 11 and 222 are homogenous. Prove that there are infinitely many homogeneous numbers that are divisible by 2008.

KBB2 Problem 5

In a triangle ABC where AB = 13, BC = 14, CA = 15, a point P is such that $\angle APB = \angle BPC = \angle CPA = 120^0$. Calculate $AP+BP+CP$

Sunday, August 16, 2009

KBB2 Problem 4

For $a,b,c$ positive reals, show that:

$\displaystyle \frac{6a}{9a^2+5(a+b+c)^2} + \frac{6b}{9b^2+5(a+b+c)^2} + \frac{6c}{9c^2+5(a+b+c)^2} \leq \frac{1}{a+b+c}$

KBB2 Problem 3

Suppose the Cartesian plane is tiled with infinitely many square tiles such that:

1. The square tiles must have the same size and form a chessboard-like formation.

2. Each tile corner must lie on a point with integer x-coordinate and y-coordinate

3. The tile sides need not be parallel to the X or Y axis.

Given that the points $(0,0)$ and $(3,1)$ are both tile corners (not necessarily of the same tile), determine all the possible tile sizes.

KBB2 Problem 2

The country of Sikinia uses gold, silver, and bronze coins as its currency. One gold coin is worth 334 silver coins, and one silver coin is worth 208 bronze coins. One day, Ali went to the store and bought an item priced at 3 gold coins. How many ways can Ali pay the item in, assuming that he has unlimited supply of gold, silver, and bronze coins?

KBB2 Problem 1

If $S_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$ for $n$ natural number, prove that:

$S_1 + S_2 + \cdots + S_n = (n+1)(S_{n+1} - 1)$

Friday, August 14, 2009

Tuymaada Yakut Olympiad, Day 2 Problem 4

The sum of several non-negative numbers is not greater than 200, while the sum of their squares is not less than 2500. Prove that among them there are four numbers whose sum is not less than 50.

OSN 2009 Problem 4

I proposed this problem to OSN (Indonesian Science Olympiad) 2009 committee and it was selected as problem #4.

There are 7 cities that are connected by a railroad network. Each railroad segment connects two cities, and each city is connected by at least 3 segments. Prove that there is a route that visits exactly 4 cities, visits them exactly once, and goes back to the city of origin.

(Example: A-B-C-D-A)