## Tuesday, October 30, 2007

### Linear Independence

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

Let the set of vectors ${a_1,a_2,...,a_n}$ be linearly independent. Prove that ${v_1,v_2,...,v_n}$ are also linearly independent given

$v_i=\sum_{cyclic} {k_i + k_{i+1} +...+k_{(i+n-1)mod n}$

I mean
$v_1=a_1 + a_2 +...+ a_{n-1}$
$v_2=a_1 + a_2 +...+ a_n$
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 :)

## Tuesday, October 23, 2007

### 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 $S={1,2,...,n}$ . In how many ways can we select non null subset of $S$ such that no two elements in the subset give difference one ?

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

$A_n = A_{n-2} + A_{n-1}$
with $A_1=1$ and $A_2=2$

It is clear that $A_n$= (n+1)th Fibonacci number,$F_{n+1}$

Looking the other way, let our subset contain $k$ elements.
$k${min, max}= {$1$, $\lfloor{(n+1)/2} \rfloor$}

I arrange all the $k$ 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 $n-2k+1$ balls with $k+1$ places available. You are getting what I am telling ?

This can be done in ${n-2k+1 + k\choose k}$ ways.
So,

$F_{n+1}$= $\sum_{k=1}^{\lfloor{(n+1)/2} \rfloor}$ ${n-k+1\choose k}$

### 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 ?

## Wednesday, October 10, 2007

### 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 $a$ and $b$ . It is clear that there cannot exist two points within the b-circle.

I go on placing $\lfloor {b/a}\rfloor$ points on the circumference of a-circle with gap of at least 'b' of course, I do not know what to do with $b/a-\lfloor {b/a}\rfloor$ . 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
$\lfloor [1/arctan(b/2a) \rfloor$ points. So the picture now looks like fig1.

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

Of course the problem is solved of if points like $A1$ 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 .

## Sunday, October 07, 2007

### Pleasure of Latex

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

$\mu^{\alpha+3} + (\alpha^{\beta}+\theta_{\gamma}+\delta+\zeta)$

$y_{i+1} = x_{i}^{2n} - \sqrt{5}x_{i-1}^{n} + \sqrt{x_{i-2}^7} -1$

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

$X_1 + X_2 +... + X_k = N$

such that $X_i for every $i$

Lets suppose $k(h-1)>N$ so that at least one solution is assured.
*************************
The flipside of this is simple. How many solutions with each

$X_i > h$ ? Easy.. put $h+1$ balls in each of the $k$ boxes, a priori. Now distribute rest in $C(N-k(h+1), k-1)$ :)
***********************************************************************
solution: Suppose $hl

Let

$p=max(l,k)$

(i) only one of the entries has size

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

$\sum_{1 till p}(-1)^{r+1}{k\choose r}{N-rh+k-1\choose k-1}$

(ii) For two,

$\sum_{2 till p}(-1)^{r+2}{k\choose r}{N-rh+k-1\choose k-1}$

and so on.

Summing up individually we get

$\sum_{odd }{k\choose r}{N-rh+k-1\choose k-1}$

Hence the number of solutions with the given restriction is

${N+k-1\choose k-1}- \sum_{odd} {k\choose r} {N-rh+k-1\choose k-1}$