The Vodafone problem

I was lazily lying on my bed thinking soon after getting up still drowsy...I have change my hutch[no vodafone] account from postpaid to prepaid. Then this thing flashed to me:

1. Now vodafone announces a scheme by which you may choose number/s and you can make calls to that number/s at concessional rate. Lets call this condition as you two are 'connected'.You choosing that number/s also means that person [ those people] can also call you at concessional rate ie., automatically 'doubly connected'. Virtually,There is no limit to the number of people you can stay connected with. I choose some 'n' arbitrary distinct people and see who are connected to whom. I write (a->b) if a and b are connected. Here is a possible map:
1->2,4
2->1,5,6
3-> nothing
.
.
.
n->15,24

How many such maps are possible?
What if remove the condition that if (a->b) does not necessarily imply (b->a) ?

2. Consider this 'special scheme' in which if (a->b) and (b->c), then (a->c). [ I know this reminds you of equivalence relation :) ]. Now how many maps under both the conditions ?

An intriguing one -II

This is the continuation of the post 'An intriguing one'. Here I make an attempt to look at a possible approach.

Consider two concentric circles with radii and . It is clear that there cannot exist two points within the b-circle.

I go on placing points on the circumference of a-circle with gap of at least 'b' of course, I do not know what to do with . As of now we shall distribute evenly. This was to give an idea. You must have figured out that we can pack still more, it is not difficult to see that we can place
points. So the picture now looks like fig1.


I have written only two circles with centers and respectively, to show available region for further points. After doing this, pick points like and in the next iteration. But analysis becomes non trivial from this step itself.

Of course the problem is solved of if points like lie within b-circle.

Miscellany: Seemingly related but a easy one i found at Colorado mathematical Olympiad

(a) We need to protect from the rain a cake that is in the shape of an equilateral triangle of side 2.1. All we have are identical tiles in the shape of an equilateral triangle of side 1. Find the smallest number of tiles needed.
(b) Suppose the cake is in the shape of an equilateral triangle of side 3.1. Will 11 tiles be enough to protect it from the rain?

I found that we require 6 and 11 .

Pleasure of Latex

Many many thanks to Wolverine for latex implementation script on Firefox.
Link to the site.

good naa.. :)

ps: But I found that same cant be used on be comments page. Anybody has a idea?

Distribution with restrictions [S]

When I wrote this post I made a typo mistake. Here is what I intended.
*******************************************************************
Problem: Enumerate the number of solutions of the equation



such that for every

Lets suppose so that at least one solution is assured.
*************************
The flipside of this is simple. How many solutions with each
? Easy.. put balls in each of the boxes, a priori. Now distribute rest in :)
***********************************************************************
solution: Suppose

Let

(i) only one of the entries has size

and rest are less than that. Now we get the regular inclusion-exclusion expression

(ii) For two,

and so on.

Summing up individually we get

Hence the number of solutions with the given restriction is

This is not going to be simple..

Consider this restricted lattice bounded by [0,0];[x,0];[x,y];[y,0]. One can move from any point to another by a path , sequence of adjacent lattice points ( like one in the bad diagram I have written). Enumerate the number of paths from [0,0] to [x,y] ( obviously within the restricted grid). What about the paths that have loops? By a loop I mean the path coming back to the point that has already been traversed. (This diagram does not have loops)

Recent problems

Of late, I have been studying a lot of combinatorics and attacking problems with enthusiasm.Here are a few worth mentioning ones.

1. Supposing there exists a convex polygon such that no three diagonals meet at a point, (i)find the number of intersections of the diagonals. (ii)Find the number of interior areas formed.

2. Enumerate the number of ways of arranging n black and n white balls around a circle. Two arrangements are considered same if one can be obtained by rotation of other.

3. Enumerate the number of ways of selecting a subset of size k (k<=n/2) out of set { 1,2,...,n} so that no two elements in the subset are adjacent elements of the original set.1 and n are considered adjacent.

4. Among n points,any two points are said to be joined to each other if they are connected by the means of a line.Such a system is called a graph. Enumerate all the graphs such we can reach any point on the graph from other by traversing through through the connecting lines in a unique way.Alternately, find the number of spanning trees.

I could completely solve 1(i) and 3. I shall soon post the solutions. Rest I am clueless :)

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'.