Convex cone

Posted on: July 31st, 2013 by
4

This puzzle requires some knowledge of Linear Algebra. Suppose $v_1, v_2, \dots v_m$ are m non-zero column vectors in $\mathbb{R}^n$ with non-negative entries. Assume the span of the m vectors is of dimension $k$. Assume $k<\text{min}(m,n)$. Consider the convex cone $\mathcal{C}=\left\{\theta_1 v_1+ \theta_2 v_2 + \dots \theta_m v_m ~~:~~\theta_i \ge 0,~i=1,2,\dots m\right\}$ Show that we can find $k$ vectors $u_1,u_2,\dots u_k$ in $\mathbb{R}^n$ with positive entries such Continue reading the story "Convex cone"

Vigilance campaign

Posted on: July 30th, 2013 by
7

A city has M roads from north-south and N roads from east-west. The roads are small enough that the entire road is visible from any point on the road. The governor wants to monitor the roads, so he wishes to place policemen at intersections. What is the minimum number of policemen needed so that the entire road network is visible? - via Math Puzzles

Divisible by 100

Posted on: July 29th, 2013 by
1

Given any 100 integers, show that one can find a subset of these 100 integers whose sum is divisible by 100. - via Moscow Math Olympiad

Matrix rank properties

Posted on: July 28th, 2013 by
1

Let A and B be any two matrices. Show that rank(A+B) <= rank(A)+rank(B) rank(AB) <= min{rank(A), rank(B)}

Square juxtaposition

Posted on: July 27th, 2013 by
Two squares are said to be juxtaposed if their intersection is either a point or a line segment. Show that any square cannot be juxtaposed to more than 8 non-overlapping squares of the same size.

Powers of 2 are all you need

Posted on: July 26th, 2013 by
1

Show that given any combination of digits, one can find a number 2^n that starts with the given combination of digits.

Divisibility

Posted on: July 25th, 2013 by
2

Suppose you arbitrarily select 101 numbers from 1,2,3,...200. Show that there exists 2 numbers among the 101 chosen numbers such that one number is divisible by the other. via Moscow Math Olympiad

Find fake coin

Posted on: July 24th, 2013 by
3

Four coins marked 1,2,3 and 5 respectively are given to you. The marks are supposed to be their weight, except that a fake coin weighs lighter than it should. There is one fake coin. Find it in 2 uses of the physical balance. via Tanya Khovanova's blog

Triangle inequality

Posted on: July 23rd, 2013 by
Let a,b,c be the sides of a triangle. Show that $\frac{3}{2} \leq \frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b} \leq 2$ Solution is found in Nick's mathematical puzzles