never resist the temptation...

I am tempted to post this problem.

Let S={ 1,2,...,n}
A and B are non empty subsets of S.
C is a subset of S with elements of form a+b where a belongs to A and b belongs to B.

Give an algorithm to generate all possible set D={ A,B}

Two not so easy ones

Take this first one from USAMO 2004.

1.Suppose are integers whose greatest common divisor is 1. Let be a set of integers with the following properties:

(a) For , .
(b) For (not necessarily distinct), .
(c) For any integers , if , then .

Prove that 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)

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

A generalization

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

x = a^k + b_k-1 a^k-1 +...+b_k-r a^k-r +..+b₀ a<sup>0

where a is a positive integer >1 and each b_i (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)</sup>

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]

A functional equation

Prove that this equation does not admit any real continuous function R ->R ( try Rⁿ->R^m)

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(x_o)=k
then , f(x_o+4)=k for arbitrary x_o and k belonging to R.
Let us select x and x+$ , two real numbers, then
epsilon=f(x)-f(x+$) = $/ (1+x)²
//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 .

This could be tough

I am told that this problem can be solved just by consideration of parity.
Let g(x) be a bijective function N->N and 'k' be any positive odd integer. Prove that there does not exist any function f(x):N->N such that
f (f(x)) = g(x) + k

Some old wine...

Well, take this old probability problem.
A mathematician carries two matchboxes(in order to complicate life!), both initially containing 'n' sticks each.Whenever a stick is needed, he takes it from one of the boxes(boxes are distinguishable)but never keeps count of matches.Once it so happens that he takes out one of the box and finds it empty, takes out the other and that is also empty.What is the probability this happening?

IISC Mathematics Integrated PhD paper 2007

You may download a copy of question paper of IISC Mathematics Integrated PhD paper 2007 held on 29th apr 2007 here ( link no longer exists!)

Finally, an easy one [S]

I caught this good one while I was having a leisurely look at mayhem taunt problems (M74).May look daunting at the first but you should be able to hit it within 10 minutes.

Problem: A circle has 12 equally spaced points on its circumference. How many ways can the numbers 1 through 12 be assigned to the points so that if the points 1 through 12 are connected with line segments, in order, the segments do not cross ? an bad example is here.[S]

An Intriguing One

Its mathematician's intuition, you look at a problem and it gives a resonance of an 'intriguing,deep impact' result. One such thing, I came across recently.

Problem: For any two positive real numbers 'a' and 'b' such that a>=b.Find the maximum number of points that can be included within the circle of radius 'a' which are separated by at least a distance 'b'.

generalized problem said, max number of points within a enclosed 'k' dimensional surface where distance between the points is greater than or equal to a given positive real number.

P.S : I am clueless.

An apparent paradox

You have infinite number of balls numbered 1,2,... at your disposal.At time(t)=0, you put balls numbered 1 to 10 into a box.At t=1/2, you put balls numbered 11 to 20 and remove ball-1 from it.Similarly at t=(1/2 + 1/4 ), you put balls numbered 21 to 30 into the box and remove ball-2 from the box.
t follows 1/2 +1/4 +1/8 +...
how many balls are present at t=1 ?

Surprisingly, number of balls in the box at t=1 is 0. For any ball numbered 'k' we can find t(=1/2 + 1/4 +...+ 1/2^k)when it is removed.
For a finite number of operations we can argue that 9 balls are added per each operation but this argument does not work when n->inf.In the language of limits,

Lt (x+9) - Lt (x) = 0
(x->inf) (x->inf)

and mind you LHS(not=)x+9-x=9

Breaking number codes

You are trying to break a four digit numeric password. You guess those four digits , if you hit the bull's eye , you are done. Else if your answer is partially correct, then you have to guess the rest of the digits in the next attempt.Can you break within three attempts?

Prove that you need at most ten attempts.

Which is the best* algorithm when you have to do the job in three attempts or <10 attempts in general ? For example we may consider the fact : probability that two same digits are present next to each other =0.216

*suppose there are two algorithms A1 and A2 which can break subsets of all four digit numbers S1 and S2.If S1 belongs to S2 then, A2 is better than A1.

An Inequality [S]

Prove that
[1/2][3/4]......[9999/10000]< 1/100
[S] See comment for solution.I have solved using the technique that is called 'telescoping'.

A probability problem [S]

Let there be a biased coin with probability 'p' of getting head and probability 'q' of getting tail.We keep tossing the coins till we get first tail(head) after a series of non zero heads(tails).

(i)Calculate the average number of tossing required. [S]
(ii)Does this function take minima when p=q=1/2. [S]

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]

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]

A false conjecture(shelved)

Observe that sum of the digits of multiples of 9 is always less than 18 atleast till surprisingly large orders of 10^10.where does this break ?( any other solution than writing a program ?)(shelved)

The train Problem[R]

You and your friend are in two adjacent boggies of a train with infinite number of boggies.Both of you donot know in which boggie the other person is.Both of you move towards front or back boggie with the intention of meeting the other.A move consists of a person moving from one boggie to other and assume that both make moves simultaneously.What is the average(expected) number of moves after which both of you meet ?[reviewing the solution...]