Average Winning Roll

$n$ people are rolling a random real number between zero and one. The highest roll wins. What is the expected value of the winning roll?

Solution: Stones and Marbles

Original problem: here

First, I apologize that the problem was not carefully worded. The problem statement should have been: find all initial conditions where it's always possible for Bob to empty all the three boxes.

There are 3 boxes, and 2010 stones and 2010 marbles are put arbitrarily inside those three boxes.

At each step, Bob is allowed to either:

1. take a stone from one box, a marble from another box, and put them on the third box

2. add or subtract all boxes by the same number of stones

3. add or subtract all boxes by the same number of marbles

Prove or disprove, that by repeating these steps, Bob can empty all three boxes.

Stones and Marbles

There are 3 boxes, and 2010 stones and 2010 marbles are put arbitrarily inside those three boxes.

At each step, Bob is allowed to either:

1. take a stone from one box, a marble from another box, and put them on the third box

2. add or subtract all boxes by the same number of stones

3. add or subtract all boxes by the same number of marbles

Prove or disprove, that by repeating these steps, Bob can empty all three boxes.

Twist And Spin

A matrix $M$ is skew-symmetric if and only if $M^{tr} = -M$. Let $S$ be the set of all 4x4 skew-symmetric matrices.

Twist

Suppose $F:\mathbb{R}^4 \to \mathbb{R}^4$ is a differentiable vector field in $\mathbb{R}^4$, we define the operation "twist" that maps each point in $\mathbb{R}^4$ to $S$ as follows:

If $F(x,y,z,w) = A\vec i + B \vec j + C \vec k + D \vec l$ then

$(\bold{twist} F)(x,y,z,w) = \left( \begin{array}{cccc}
0 & B_x - A_y & C_x - A_z & D_x - A_w \\
A_y-B_x & 0 & C_y - B_z & D_y - B_w \\
A_z-C_x & B_z - C_y & 0 & D_z - C_w \\
A_w - D_x & B_w - D_y & C_w - D_z & 0 \end{array} \right) $

Where $B_x$ denotes $\partial B / \partial x$ and so on. One way that makes it easier to memorize the formula is to associate the first column and row with $x$, second column and row with $y$, third with $z$, and last with $w$.

Spin

If $G : \mathbb{R}^4 \to S$ is a differentiable function that takes a point in $\mathbb{R}^4$ to a skew-symmetric matrix, we define the operation "spin" that produces a vector field in $\mathbb{R}^4$ as follows:

If $G(x,y,z,w) = \{ \sum_{i,j} G_{ij}(x,y,z,w) \}$ (where $G_{ij}$ is the entry at the $i$-th row and $j$-th column, and since $G$ is skew-symmetric, then $G_{i,i} = 0$ and $G_{ji} = -G_{ij}$)

Then

$(\bold{spin} G)(x,y,z,w) = (G_{23_w} + G_{34_y} + G_{42_z}) \vec i $

$+(G_{13_w} + G_{34_x} + G_{41_z}) \vec j$

$+(G_{12_w} + G_{24_x} + G_{41_y}) \vec k$

$+(G_{12_z} + G_{23_x} + G_{31_y}) \vec l$

where again $G_{ij_x}$ denotes $\partial G_{ij} / \partial x$ and so on.

Problems:

Prove the following:

1. $(\bold{spin}(\bold{twist} F)) = \vec 0$

2. $\bigtriangledown \cdot ( \bold{spin} G) = 0$

3. If $F$ is a conservative vector field, then $\bold{twist} F = \vec 0$

Dissecting a tetrahedron

Let $T_r$ denote a regular tetrahedron whose side length is $r$.

1. Prove that it is impossible to assemble eight $T_1$ into a $T_2$.

2. Prove that a tetrahedron can be cut into four optically congruent pieces. Two solids $A$ and $B$ are considered optically congruent if either $A$ or its mirror image can be rotated into $B$.

3. Prove that a $T_2$ can be cut into four $T_1$ and a regular octahedron whose side length is 1.

Solution: Inequality

Original problem: http://dharmath.thehendrata.com/2009/12/02/inequality/

For positive real number $a,b,c$ prove that

$2\sqrt{ab+bc+ca} \leq \sqrt{3} \sqrt[3]{(a+b)(b+c)(c+a)}$

Inequality

For positive real number $a,b,c$ prove that

$2\sqrt{ab+bc+ca} \leq \sqrt{3} \sqrt[3]{(a+b)(b+c)(c+a)}$

solution: http://dharmath.thehendrata.com/2009/12/02/solution-inequality/

Solution: 3 Variable Inequality

Original problem: http://dharmath.thehendrata.com/2009/11/24/3-variable-inequality/

For $a,b,c > 0$, prove that:

$! (ab(a+b) + bc(b+c) + ca(c+a))^2 \geq 4abc(a+b+c)(a^2+b^2+c^2)$

Solution: Integer Inequality

Original problem: http://dharmath.thehendrata.com/2009/11/27/integer-inequality/

For any positive real number $t$, prove that there are integers $a,b,c,d$ such that

$! a^3b+b^3c+c^3d < tabcd$

System Change

Starting with today, I am going to change the system at which problems and solutions are posted, to avoid spoiling solutions for people who do not want to be spoiled.

For each problem post, there will be a corresponding solution post, with category Solution. The two posts will refer to each other.

The problem post will simply post the problem and a link to the solution post.

The solution post will repeat the problem, and then post the solution behind a "More" link.

Integer Inequality

For any positive real number $t$, prove that there are integers $a,b,c,d$ such that

$! a^3b+b^3c+c^3d < tabcd$

Solution: http://dharmath.thehendrata.com/2009/11/30/solution-integer-inequality/

Polynomial Algorithm

Credit for this problem goes to Zeke Chin

Does there exist an algorithm for the decision problem:

Given a polynomial over $n$ variables $x_1,\cdots,x_n$ with positive integer coefficients, and a positive integer $c$, is it true that $cx_1\cdots x_n \leq P(x_1,\cdots,x_n)$ for all assignments of positive integers to $x_1,\cdots,x_n$?

For example, for $P = x_1^2 + x_2^2$ and $c=2$, the algorithm should return "Yes" since $2x_1x_2 \leq x_1^2 + x_2^2$

3 Variable Inequality

For $a,b,c > 0$, prove that:

$! (ab(a+b) + bc(b+c) + ca(c+a))^2 \geq 4abc(a+b+c)(a^2+b^2+c^2)$

Solution: http://dharmath.thehendrata.com/2009/11/30/solution-3-variable-inequality/

Mean of Means

If $a_i,b_i$ are positive numbers for $i=1,\cdots,n$, and

$! M_r (a,b) = \left( \frac{a^r+b^r}{2} \right)^\frac{1}{r}$

Prove that for $0 < r < s$,

$! \displaystyle \sum M_r(a_i,b_i) \sum M_{-r}(a_i,b_i) \leq \sum M_s(a_i,b_i) \sum M_{-s}(a_i,b_i) \leq \sum a_i \sum b_i$

Triangle Inequality

Given $n$ right triangles each with sides $a_i, b_i, c_i$, with $c_i$ being the hypotenuse ($i=1,\cdots, n)$. Let $A = \sum a_i, B = \sum b_i, C= \sum c_i$.

Prove that

$\displaystyle \frac{a_1b_1}{c_1} + \cdots + \frac{a_nb_n}{c_n} \leq \frac{AB}{\sqrt{A^2+B^2}}$

Harder version: prove that

$\displaystyle \frac{a_1b_1}{c_1} + \cdots + \frac{a_nb_n}{c_n} \leq \frac{AB}{C}$

3 Sequence Inequality

If $a_i, b_i, c_i$ are sequences of positive numbers for $i = 1,2,\cdots,n$, prove the following inequality:

$\sum (a_i+b_i+c_i) \sum \frac{a_ib_i + b_ic_i+ c_ia_i}{a_i+b_i+c_i} \sum \frac{a_ib_ic_i}{a_ib_i + b_ic_i+ c_ia_i} \leq \sum a_i \sum b_i \sum c_i$

where all summations are taken from $i=1$ to $i=n$. When does equality happen?

Matching Binary String

We are given two binary strings $A$ and $B$ each of length $2n$. Both strings contain equal number of ones and zeros to each other. We write $A$ on top of $B$, so that each element of $A$ is paired with each element of $B$ at the corresponding position.

We call the two strings a "match" if there are at least $n$ common elements where the element of $A$ at a certain position matches that of $B$ at that position.

Prove that, we can cyclically shift $B$ a number of times (and wrap around at the end/beginning) so that $A$ and $B$ form a match.

Simplifying Series

Let $a_n = \binom{2n}{n}$ and $b_n = \binom{3n}{n}$. Find a more compact expression for:

$A(x) = a_0 + a_1x + a_2x^2 +\cdots + a_nx^n + \cdots$

$B(x) = b_0 + b_1x + b_2x^2 +\cdots + b_nx^n + \cdots$

ABC String

How many strings of A's, B's, and C's are there that satisfy the following conditions:

1. There are $n$ A's and $2n$ total of B's and C's.

2. Every two adjacent letters are different.

Coin Toss

A boy tosses a fair coin repeatedly. Every time he gets a Head, he earns 1 penny, and every time he gets a Tail, he earns 2 pennies. He starts with no money. Prove that the probability of him at one time having exactly $n$ pennies is $\frac{2+(-\frac{1}{2})^n}{3}$

Path and Parallelogram

A path from $A$ to $B$ consists of several piecewise straight segments (where $b \neq A$). A flea starts from point $P$ and for each segment, it performs the following operation:

If the segment starts at $X$ and ends at $Y$, and the flea is currently at $Z$, the flea will jump to the point $Z'$ such that $XZYZ'$ is a parallelogram (in that order).

The flea starts from $P$ and performs the operation on the segments sequentially until it is done with the last segment, where the flea is now in $Q$. Prove that $APBQ$ is a parallelogram.

Integral

Evaluate $ \int e^x \sec x \tan^2x dx$

Divide Colored Balls

There are $2n$ balls of each color: red, green, and blue. How many ways are there to divide them into two groups such that each group has $3n$ balls?

First Solution

It is the same as the coefficient of $3n$ in the expansion $(1+x+x^2+x^3+\cdots+x^{2n})^3$. The proof is left to the readers as an exercise.


Note that $(1+x+\cdots+x^{2n})^3 = \frac{(1-x^{2n+1})^3}{(1-x)^3} = (1 - 3x^{2n+1} + 3x^{4n+2} - x^{6n+3})(1-x)^{-3}$

But $(1-x)^{-3} = (1+3x + 6x^2 + 10x^3 + \cdots + \frac{(k+2)(k+1)}{2}x^k + cdots)$

So the coefficient of $3n$ in that expansion is:

$\frac{(3n+2)(3n+1)}{2} - 3\frac{n(n+1)}{2} = 3n^2 + 3n + 1$

Second Solution

We shall prove that there are $3n^2+3n+1 = (n+1)^3 - n^3$ ways, which has striking geometrical interpretations.

Create an equilateral triangle with altitude $3n$, and mark all the points that has integer distance to all the sides. These points will form a triangular lattice

It is a well-known fact that for any point in an equilateral triangle, the sum of distances to the sides is constant. Since the altitude of the triangle is $3n$, then for any point in that triangular lattice, the sum of distance to the sides is $3n$. Furthermore, the distances are integers. Thus, these points represent the number of ways to choose $3n$ balls from 3 colors.

However, the constraint that we only have $2n$ supply of each color is not yet enforced. We examine the points in the lattice whose distance to any of the sides is greater than $2n$, and we eliminate them. So we are left with a hexagonal lattice of side $n+1$. This is the projection of a half-shell of an $n+1$-cube that has $n$-cube carved out of it.

Students in a School

There are 3 schools, each of which has $n$ students. Each student knows altogether $n+1$ students from the other two schools. Prove that we can choose 3 students, each from a different school, such that they know each other.

Passengers Boarding Airplane, Part Deux

2009 passengers are waiting in a line to board an airplane with 2009 seats. The seats are numbered from 1 to 2009. Each passenger has a boarding pass that has his/her seat number on it. However, these passengers are oblivious to their boarding pass and choose their seats at random, each with a uniform probability from the available empty seats.

What is the probability that everyone's actual seat number and their assigned seat number differ by at most 1? That is, no one sits more than 1 seat away from their assigned seat.

2 Variable Recursion

This problem is written as an auxiliary lemma for the solution to this problem.

Suppose $f(m,n)$ is a function that is defined for non-negative integers $m,n$ where:

$f(m,n) = 0$ if $m < n$

$f(m,0) = 1 \forall m$

$\displaystyle f(m,n) = \sum_{k=1}^{n} f(k-1,k-1) f(m-k,n-k) + f(m-1,n) \forall m \geq n$

Prove that $f(m,n) = \frac{m-n+1}{m+1} \binom{m+n}{m}$

Combinatorial Sum Identity

For $m,n > 0$ prove that

$\displaystyle 1 + \sum_{k=1}^{m} \binom{k+n}{k} = \binom{m+n+1}{m}$

Harder version:

$\displaystyle \sum_{k=l}^{m} \binom{k+n}{k} = \binom{m+n+1}{n+1} - \binom{n+l}{n+1}$

Boys and Girls around the table

$(n+1)$ boys and $n$ girls are seated around a circular table playing a game. One boy started to put a stone on the table, and they subsequently went around the table clockwise. At each child's turn, if that child is a boy, he puts a stone on the table, but if that child is a girl, she takes away one stone from the table. They're finished when everyone has had one turn. If the table ever becomes empty (except before the first boy put his stone), they all lose the game.

Prove that there is a boy such that if he starts, they can complete the round without losing.

Furthermore, prove that there is only one such boy. That is, if any other boy starts, they would lose the game.

Harder version: suppose you now have $m+n$ boys and $n$ girls, with $m$ positive. Prove that there are exactly $m$ boys who could start a non-losing game.

Circles and Coloring

Several circles are drawn on a piece of paper to form several regions on the paper. We wish to color these regions such that no two regions that share a common boundary would have the same color.

(It is okay if two regions that share a common point to have the same color, but not boundary)

How many colors minimum are needed?

Show and Change

Credit for this problem goes to a friend of Boon Leong Ng.

A ticket to a show costs 10 dollars. There are $(m+n)$ (where $m > n$) people waiting on a line. $m$ of them pays with 10 dollar bills and $n$ of them pays with 20 dollar bills. Assuming that the cashier starts out with no money, what is the probability that the cashier never runs out of change? Assuming the probability is uniform among all possible ordering of people.

Passengers Boarding Airplane

2009 passengers are waiting in a line to board an airplane with 2009 seats. Each passenger has a boarding pass that has his/her seat number on it. The first passenger, however, was oblivious and chose a random seat to sit on.

For each subsequent passenger, he/she will try to sit on his/her assigned seat first. If that seat is taken by someone else, he/she will choose a random empty seat to sit on.

What is the probability that the last passenger would sit on his assigned seat?

Solution: http://dharmath.blogspot.com/2010/05/solution-passengers-boarding-airplane.html

Room and Lights Game

This problem is identical to this one but reworded for better clarity.

Alice is playing a game against Bob and Charlie. In a room, there are 27 lights with individual switches, some of them could be turned on or off. Bob enters the room while Charlie waits outside. Alice will tell Bob a number from 1 to 27. Bob then is allowed to flip at most 3 switches if he wishes. Then Bob exits and Charlie enters the room. He has to, upon examining the lights, guess the number that Alice told Bob. Neither Bob nor Charlie knows the configuration of the lights before Bob entered the room.

How can Bob and Charlie agree on a strategy to win this game?

Harder version: 15 lights, but Alice tells Bob a number from 1 to 16, and Bob can only flip at most one switch.

Spy And Radio

A spy is being commissioned by the government to infiltrate a mafia rank in order to find out who the head honcho is. There are sixteen potential candidates and the government needs to know which one of them is the leader. However, the spy only has one chance to pass the information back to the government before she gets murdered.

On an previously-agreed date, the local radio station will announce the winning lottery number. This number will be from 0 to $2^{15}-1$ inclusive, and will be saved as a 15 binary digit data in that radio station's computer. The spy only has one chance to infiltrate the radio station's computer mainframe, change one bit (or none) in that number, and leave. The broadcaster will announce the number without knowing that the spy has changed it, and the government agents will listen to that changed number. The government and the spy don't know the winning number in advance and they have no further power to rig the lottery.

To make things more complicated, the spy does not have that much time in the radio station's computer room. Therefore, she would not be able to perform lengthy and complex calculations. Of course, lengthy and complex is a relative term, but she is a sufficiently accomplished mathematician and she needs to perform this task in less than one minute.

What strategy can be done by the spy and the government so that she can pass the mafia leader's identity accurately with that one chance?

Remark: The following weaker versions of the problem are due to David Rager:

1. Prove that if there are 3 mafia members and 3 bit number lottery winner, you can pass the information with only 1 flip.

2. Prove that if there are 27 mafia members and 27 bit number lottery winner, you can pass the information with only 3 flips.

Prisoners and hats

2047 prisoners are kept in a dungeon. One day, the King decided to do an experiment. They will each be given either a blue hat or a red hat and then collected in a room. Each prisoner can see the color of everyone else's hats but not his own. No form of communication is allowed. After a few minutes, the warden will come and ask each of them individually what he thinks the color of his hat is. They can answer "red" or "blue." Each prisoner must answer by whispering to the warden's ear, so that the other prisoners can't hear his answer. Those who can answer correctly will be freed, but those who answer incorrectly will be executed on the spot. The prisoners found out about this experiment the night before, so they had some time to devise a scheme to ensure they can save as many people as possible.

Question 1: What is the scheme that allows everyone to live in this case?

Suppose now the King decided to alter the experiment a little bit. The warden will come to the room immediately after everyone get their hats. Each prisoner is allowed to answer "red", "blue", or "I don't know." If everyone answers "I don't know", they will all be executed. If someone answers "red" or "blue" and he is wrong, they will all be executed. Otherwise, everyone is freed at the same time. In other words, in order for them to live, at least one person must answer "red" or "blue" and he must be right. As before, the prisoners can't hear everyone's answers, and the release or execution is delayed until everyone had given their answers.

Question 2: What is the scheme that allows everyone to live with the highest probability? What is that probability?

Gas stations on a circular track

On a circular track, there are several gas stations. The total amount of gas in all these stations are just enough for a car to complete one lap. Prove that, starting with an empty car, one can choose an initial position such that he can complete the lap by subsequently filling gas in these stations.

Black and white painted sphere

The surface of a sphere is painted with black and white paints such that the area of black paint is less than 1/8 of the area of the sphere (the rest of the sphere is painted with white). Prove that one can inscribe a rectangular box in the sphere such that all eight corners land on white points.

More formally, if each point on the sphere is assigned a color black or white such that there is an injective but not surjective one-to-eight unordered mapping from the black points to the white points, prove that there are eight white points on the sphere that form a rectangular box.

a b c sides of a triangle, perimeter less than 2

If $a,b,c$ are sides of a triangle whose perimeter is less than 2, prove that:

$\displaystyle \frac{(1+a)(1+b)(1+c)}{(1-a)(1-b)(1-c)} < \frac{(2+a+b+c)^2}{(2-(a+b+c))^2}$

Polynomial not sum of squares

Let $P(x,y) = x^2y^4 + x^4y^2 + 1 - 3x^2y^2$

a.) Prove that $P(x,y)$ is non-negative

b.) Prove that $P(x,y)$ cannot be expressed as a sum of squares of polynomials.

n-expressible integers

A positive integer is called $n$-expressible if it can be written as a sum of $n$ or less squares.

Prove that the product of two $n$-expressible integers is $\frac{n^2-n+2}{2}$-expressible

Non-negative polynomials as sums of squares

Prove that any non-negative real polynomials can be expressed as a sum of squares.

More formally, if $P(x)$ is a polynomial with real coefficients such that $P(x) \geq 0 \forall x \in \mathbb{R}$, show that there exist $Q_1,Q_2,\cdots, Q_k$ polynomials with real coefficients such that $P(x) \equiv Q_1^2(x) + Q_2^2(x) + \cdots + Q_k^2(x)$.

Variant of KBB3 Problem 4

This is a harder version of KBB3 Problem 4.

Suppose $n$ is an odd positive integer. Given an $n \times n$ chessboard where each cell is colored black or white. At any step, we are allowed to pick any cell and flip the colors of the cells that are in the same row or the same column as that cell. Prove or disprove: no matter what the initial coloring is, we can always get an all-white board?

OSN Proposal: Inequality

I proposed this problem to OSN 2009 but it was not selected.

For $a,b,c$ positive numbers such that $a+b+c=3$, prove that:

$2(a^{11} + b^{11} + c^{11}) + 3a^3b^3c^3(ab+bc+ca) \geq 5(a^4b^4 + b^4c^4 + c^4a^4)$

Inequality of The Day

For $a,b,x,y$ real numbers, prove that:

$(3a^2+2ab+5b^2)(3x^2 + 2xy + 5y^2) \geq (3ax + ay + bx + 5by)^2$

Generalization: for $a,b,x,y$ real numbers, and $P,Q,R$ real numbers such that $Q^2 < PR$, prove that:

$(Pa^2+2Qab+Rb^2)(Px^2 + 2Qxy + Ry^2) \geq (Pax + Qay + Qbx + Rby)^2$

KBB3 Problem 4

Given a 3x3 chessboard where each cell is colored black or white. At any step, we are allowed to pick any column or any row and flip all the cell colors in that column or row. Prove or disprove: no matter what the initial coloring is, we can always get an all-white board?

KBB3 Problem 3

In a triangle $ABC$, $D$ is the midpoint of $BC$. $O_1$ is the circumcenter of $ABD$ and $O_2$ is the circumcenter of $ACD$.

$M$ is the midpoint of arc $BD$ opposite from $A$.

$N$ is the midpoint of arc $CD$ opposite from $A$.

$P$ is the midpoint of arc $AB$ opposite from $D$.

$Q$ is the midpoint of arc $AC$ opposite from $D$.

$R$ on the circumcircle of $ABD$ such that $O_1R \perp AC$.

$O_1$ and $R$ are on different sides of $AC$ or its extension.

$S$ on the circumcircle of $ACD$ such that $O_2S \perp AB$.

$O_2$ and $S$ are on different sides of $AB$ or its extension.

Prove that $MN, PS, $ and $QR$ are concurrent.

KBB3 Problem 2

Given $x_1, \cdots, x_n, y_1, \cdots y_n$ non-negative real numbers such that:

$x_1 + \cdots + x_n = 1$

$x_1y_1 + \cdots + x_ny_n = n^2$

Find the minimum value of

$\displaystyle \frac{x_1(y_1^2 + n^2)}{y_1 + 1} + \cdots + \frac{x_n(y_n^2 + n^2)}{y_n + 1}$

KBB3 Problem 1

Find the smallest prime number that divides $54^{54} + 55^{55} + 56^{56}$

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.

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!$?

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.

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$

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)$

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)