Tuesday, June 26, 2007

Two not so easy ones

Take this first one from USAMO 2004.

1.
Suppose a_1, \dots, a_n are integers whose greatest common divisor is 1. Let S be a set of integers with the following properties:

(a) For i=1, \dots, n, a_i \in S.
(b) For i,j = 1, \dots, n (not necessarily distinct), a_i - a_j \in S.
(c) For any integers x,y \in S, if x+y \in S, then x-y \in S.

Prove that S must be equal to the set of all integers.
*****************************************************

If you hit the above one, try this, as of now I haven't got it yet.

2.
A friend of mine is organizing a board game tournament with 5 rounds. There are 12 competing players. One of the games is a 6-player game. The other 4 games are different 4-player games. My friend has enough copies of every game, so each round will be played with multiple parallel game tables.

The question is: can he assign the players to the tables in such a way that
every player plays every other player exactly 1 or 2 times during the tournament? "Playing" means: sitting at the same table during any round.

So, the assignment should look like this:

round1: XXXXXX XXXXXX (2 tables of 6 people each)

round2: XXXX XXXX XXXX (3 tables of 4 people each)

round3: XXXX XXXX XXXX

round4: XXXX XXXX XXXX

round5: XXXX XXXX XXXX

I hope someone finds a solution for my friend!!

(courtesy :Big fury monster)

Friday, June 15, 2007

pretty good

Prove that among any 10 consecutive integers at least one is relatively prime to each of the others.





hint: picture has nothing to do with the problem

Tuesday, June 12, 2007

A generalization

Prove that any positive integer x lying between ak and ak+1 can be represented uniquely as follows

x = ak + bk-1 ak-1 +...+bk-r ak-r +..+b0 a0

where a is a positive integer >1 and each bi (non negative integer) is less than a.

I generalized this based on the problems found in Niven's number theory book( pg 19 pro, 44 and 45 , fifth edition)

Thursday, June 07, 2007

A simple one [S]

This objective type question is said to have appeared in one of the old ISI selection papers.
A club with 'x' members is organized into 4 committees such that
[a] each member is in exactly two committees
[b] any two committees have exactly one member in common

Then,
1. exactly two values both between 4 and 8.
2. exactly one value lying between 4 and 8.
3. exactly two values between 8 and 16.
4. exactly one value between 8 and 16. [S]

Tuesday, June 05, 2007

A functional equation

Prove that this equation does not admit any real continuous function R ->R ( try Rn->Rm)

f(x).f(x+1) + f(x) + 1 = 0

My progress so far: turn this into a recursive equation
f(x+1)= -1/ [ f(x) +1]
suppose if f(xo)=k
then , f(xo+4)=k for arbitrary xo and k belonging to R.
Let us select x and x+$ , two real numbers, then
epsilon=f(x)-f(x+$) = $/ (1+x)2
//neglecting $ as it does not matter in the analysis that follows//
if x is negative and greater than -1, epsilon> $.
will this help? am not able to proceed from here .