Monday, November 27, 2006

A beautiful problem [S]

I found this problem in Bay area mathematical olympiad 2006.The solution hardly needs any mathematics(the way I solved), classic example of pure thought.
Problem:All the chairs in a classroom are arranged in a square n×n array (in other words, n columns and n rows),
and every chair is occupied by a student. The teacher decides to rearrange the students according to the
following two rules:
(a) Every student must move to a new chair.
(b) A student can only move to an adjacent chair in the same row or to an adjacent chair in the same
column. In other words, each student can move only one chair horizontally or vertically.
(Note that the rules above allow two students in adjacent chairs to exchange places.)
Show that this procedure can be done if n is even, and cannot be done if n is odd.[S]

Tuesday, November 14, 2006

Special case is difficult than the general case [S]

Consider the traditional combinatorial problem

How many non-negative solutions does this equation have ?

X_1 + X_2 +....+X_n = N

For example, X_1 + X_2 = 10
Let me write a string of ten zeroes.
0 0 0 0 0 0 0 0 0 0

Let me insert 1 in any of the 11 available positions adjacent to any of the zeroes.This 1 acts as a separator, thus giving the value of X_1 and X_2.Hence there are (10+1)C 1 ways to arrange ie,. 11 solutions.

generalizing the same
original equation has (N+n-1)C(n-1) solutions.

How many solutions are there if X_i < style="color: rgb(255, 0, 0);">[S]

Circle n arc [S]

Say, we have a circle of radius 'a'. Now, draw an arc of a circle of radius 'b' such that its centre lies on the circumference of the first circle, and the end points of the arc are on the circumference as well, as shown below.Here comes the question: What is the ratio of b/a, such that, the area of the blue region is equal to that of the red region.

I wrote a python program and found out that the ratio is constant (=1.159). But, i could not figure out a proper theoretical proof. Im hoping that someone will do it in the comments box.

P.S: A special thanks for Sushama for asking me this cute problem, which fortunately or unfortunately, she doesnt have an answer to.[S]