Goodbye math blog

To whomsoever it may concern,

I have finally decided to stop writing this math blog. This has no bearing on rest of the contributors. It has been a great journey, I see myself today with a lot more mathematical maturity as I go through old to new posts. The reason to stop is not because I am getting absorbed into more serious math but the lack of purpose for which the blog was created nearly two years ago. ( I feel it is the time to tell the story, how the blog started) I had started messaging friends some curious problems that I normally kept creating for fun, later Sudhir suggested 'why don't you blog?' as it reaches people and people can comment. From then on I have posting problems mostly recreational, though I agree that my recent posts were a bit serious.

But these days there has been no response, comments like before and therefor feel the blog does not serve the purpose it was created for. I did or do not expect that I get comments that are mathematical, but some 'tries' as many of them are reachable to a layman, neither I feel like writing about what problems I am thinking about. So

Yours,
Srikanth

New books in mathematics

You can find a lot of free e-books here.Books range from math classics to recently released ones gracefully violating copyrights.I simply believe knowledge should be free.

Some good books of my interest:

1.The art of Counting - Paul Erdos.

2.Combinatorics - Peter Cameron.

3.A course in combinatorics - van Lint and Wilson

4.Enumerative Combinatorics - R P Stanley

5.Research Problems in Discrete geometry - Peter Brass et al

klien's problem

I found this problem asing to be attacked by PHP, later I learnt this was generalized by Erdos and Szekeres(happy ending problem).

Let there be 5 points arbitrarily lying on a plane.Prove that we can find four points that form a convex quadrilateral.

classic proof: If the smallest convex polygon encompassing all the points is quadrilateral or pentagon, then we are done. Else, if it is a triangle (say ABC) and D and E are interior points.Among three points A, B, C two points lie on one side of DE and we are done.

Another proof:(I feel this is not elegant as the previous one)

Let three points A,B,C form a triangle.Now I think how I can introduce the 4th point.Reffering to pic1 if I introduce the 4th point in the non red regions we are done. So let me proceed by putting 4th point in red region. This results in pic2 that is equivalent to introducing the 4th point within triangle ABC.

If the 5th point is introduced outside triangle ABC we are done.Else if introduced within ABC we get a convex quadrilateral involving D.

Hit by PHP (Pigeon hole principle)

Problem: For coprime a and b, a/b has period of reccurance of length atmost b-1.

This next one is a classic.
Let there be n integers not necessarily distinct.Prove that we pick k (< (n+1)) integers which is divisible by n.

Let i_1, i_2,..., i_n be the integers.

Let a_1=i_1,
a_2=i_1 + i_2
.
.
a_n=i_1+..+i_n

If one of the a_j ( j=1,..,n ) is divisible by n we are done,else by php we can find a_r and a_s (r>s)giving same remainder. Then a_r-a_s gives rem 0 and we are done.

Yet another counting problem

This seems to fall for computation, I am looking at a possible elegant solution.

Problem:Let us have a n*n square.Two squares(both of dimension less than n*n)form an unordered pair if

(i) They have atleast one 1*1 square common.

(ii)One is not contained in the other.

Compute the number of unordered pairs.

(nothing sacred about squares, rectangles must make the problem tougher)

Computing a few Invertible matrices

Problem: Enumerate and generate the number of invertible matrices (n*n) with each entry either 0 or 1.

Example: For n=2, we have a set of 6 matrices. They are

Interestingly, these matrices form a group under matrix multiplication.

A much more harder problem would be to enumerate and generate all invertible (n*n) matrices with enrites fron the set { 0,1,...,n-1 }.

Linear Independence

This problem is the generalization of exercise 2.3.9 from 'linear algebra' Hoffman and Kunze.

Let the set of vectors be linearly independent. Prove that are also linearly independent given



I mean


and so on.

ps: I proved it by proving a certain matrix to be invertible and that was pretty cumbersome. Hoping for a better pretty solution :)

A closed form for nth Fibonacci number

I have made an attempt to arrive at a closed form by setting up a bijection in a counting process.

Consider the set . In how many ways can we select non null subset of such that no two elements in the subset give difference one ?

Let be the number of ways of selecting such a subset. Depending upon whether is included in the subset or not , we get


with and

It is clear that = (n+1)th Fibonacci number,

Looking the other way, let our subset contain elements.
{min, max}= {, }

I arrange all the elements in ascending order from left to right. Except for the last element, I place a ball just right of each element. Now I am left with balls with places available. You are getting what I am telling ?

This can be done in ways.
So,

=

Oh ! I forgot to tell

I would like to welcome our new Contributor - Gangotryi.

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