## Archive for the ‘math’ Category

### Puzzle : Scaling a Square!

October 20, 2011

It’s been a while since I posted anything here. In addition to me being lazy and busy, I did not encounter any nice puzzle.  This puzzle, again given to me by Ramprasad, who got it from someone when he attended China Theory Week. This is one of those puzzles that you will curse yourself for eternity if you do not get it. The solution is so simple that if you can’t get it, you should die of shame!! Surprisingly, many Professors who attended CTW could not get it. Anyways, without further ado here it goes.

Problem : On a table you have a square made of 4 coins at the corner at distance 1. So, the square is of size 1×1.  In a valid move, you can choose any two coin let’s call them mirror and jumper. Now, you move the jumper in a new position which is its mirror image with respect to mirror. That is, imagine that mirror is a centre of a circle and the jumper is on the periphery. You move the jumper to a diagonally opposite point on that circle. With any number of valid moves, can you form a square of size 2×2? If yes, how? If no, why not?

Solution : My first intuition told me that no matter how many moves you take, you can never make a square of size 2×2. But why? Initially, I went on different directions like, putting a bound on the distances between the coin. Well, the distances between the coin can grow in an unbounded manner. What about an Area? Can we put a bound on the area trapped inside the convex hull formed by these 4 coins? If we can show that area can not grow upto 4x the originial size, we are done. But well, you can not even put a bound on the area. I leave it as an exercise to show how distances and area can grow in an unbounded manner.

One point to note is that instead of a square, if it is triangle, the area will remain constant, always!!

Anyways, here is the solution for those who have given up or who just wants to verify whether their solution is correct. Note, that every valid move is reversible. That is if you make a move in one direction, the other direction is also a possibility. So, if you can scale a square of size 1×1 into a square of size 2×2, then you should also be able to shrink it into arbitrary small square. Say 1/2 x 1/2 or 1/1024 x 1/1024.

So, now we need to show that you can not shrink the square. If we show that distance between any two coins is always greater than 1 unit, we are done. And here is the most simple part!

Imagine a grid on the 2-d plane. Let the coins be at (0,0) (0,1) (1,0) (1,1) forming a square of size 1×1. Our grid cells are of size 1×1. Note, that no matter how many moves you make, the coins will always have integer co-ordinates ( basically stays on the grid ). Since, the shortest distance on the grid is 1 unit, no two coins can have distance shorter than 1 unit. And we are done!

— Saurabh Joshi

### Points on a grid

February 25, 2011

Hi,

This is again one of the question that tejas faced in the CMI entrance exam.

Problem : Given an nxn grid. You choose 2n-1 points randomly ( each with different co-ordinates on the grid ). Prove that there will be three points amongst these 2n-1 point forming a right-angle triangle.

Solution :

It is easy to see that if we prove that it always have to be the case that there will be a point sharing a column with one point and a row with another point we are done. Looks like good old pigeon hole principle (php) should come to the rescue. Unfortunately, I could not come up with a solution using php.

I used mathematical induction to come up with a proof. And I agree with many other people who say that it does not give much insight into the problem.  Anyways, here it goes.

I am going to prove a general claim.

Claim : If you choose m+n-1 points from an mxn grid, there will be three points forming a right angle triangle.

Base case : 2×2 grid ( does not make sense when m or n is 1 ). This is trivial because we have to choose 3 points.

Also, 2xn is also trivial. We have n+1 points. Using php it is easy to see that there will be two points on the same row and two points on the same column. Because there are only two rows, it has to form a triangle. Similar argument goes for mx2 grid.

Assume that the claim is true for any m-1xn-1 grid.

Now,

(1) choose a point p at (x,y) which does not share either a row or column with any other point.  Remove the column and row denoted by x and y. Now we have m-1Xn-1 grid with m+n-2 (= (m-1) + (n-1) – 1  + 1) points to choose from. Follows from induction hypothesis.

(2) choose a point p at (x,y) which shares the column x ( or row y) with only one another point p1. If p also share a row(or column) with some other point p2, we are done. If not, remove column x and row y. m-1xn-1 grid with m+n-3 = (m-1 +n-1 -1) points to choose from. Follows from induction hypothesis.

(3) There are points p1…pk in the same row ( or column ). One can see that there can not be a point p in any of the column of p1…pk. Hence, remove all columns of p1…pk and the row in question. Now, grid is m-1 X n-k with m+n-1-k ( = m-1 + n-k -1 + 1 ) points to choose from. Follows from the induction hypothesis.

I know that there must be extremely simple proof for this. Arrgh, unable to find it :(.

–Saurabh Joshi

### Puzzle : A number game

February 24, 2011

Well,

This is comparatively a simple puzzle with a nice observation. Given to me by tejas, who in turn, faced it in an entrance exam of CMI.

Problem : You are given integers from 1…2n. You are supposed to divide it in two sub sequence A and B such that, A and B both are of the same size n. A is monotonically increasing and B is monotonically decreasing. Prove that,

for any two such sequences $\sum _{i=1} ^n | A[i] - B[i] | = n^2$.

Solution : A very simple observation and you have the solution. Let,  $\sum _{i=n+1} ^{2n} i - \sum _{i=1} ^n i=n^2$. So here is what you do. The moment you observe that A[i] > B[i] for some i, you swap the elements. So the element at A[i] is now in B[i] and vice versa. Thus, you can make sure that set A has all and only elements from 1…n and B has all and only elements from n+1….2n. Note, that the difference is taken over the absolute value, hence swapping does not change it. Now we know that difference between summation of elements of B and A is $n^2$.

Neat, isn’t it?

–Saurabh Joshi

### Puzzle : Black and White hats!

January 3, 2011

Hi,

This very nice puzzle was brought to me by Ramprasad.

Problem : Set of people ( infinite ) are standing on a line of natural numbers. That is they are standing at position 1, 2, 3 …. and so on. White or black hats are put randomly on all of them. What strategy can they decide on so that either all of them guess the color of their hat right, or none of them get it right?

Solution : I hope you guyz remember another puzzle on the similar lines. In fact, you better read that post and I am going to refer to the strategy employed there. Remember that in that earlier puzzle, they have to come up with a strategy so that only finitely many of them guesses it wrong. So we partitioned set of all strings into groups such that strings belonging to one group are only finite hamming distance away from each other. And then using axiom of choice we have a representative strings C1,C2…. in each group.

Now, the hint is, suppose you are one of the people standing. What additional information do you need to know whether you guessed it right or wrong? Think about it.

Well, if someone tells you the hamming distance of the string S ( in which you belong ) and the representative string Ci, then you know whether you guessed it right or wrong. Because, if you see that S’ ( all but you ) differs from the representative string by distance d, then you have guessed your color right. If you see the difference at d-1 position, then you know that you are in one of the position where two strings differ so you must have guessed it wrong.

There you go! That is the hint. All of them decide on to guess that the string S differs only at d locations where d is odd. Now, if S differs at locations d’ where d’ is even. All those people at position which does not differ from representative string Ci, they will see the difference of d’. But as decided, they will try to make the distance odd, so they will choose the opposite color as given by the representative string. Hence, all of them will guess it wrong. For a person who is in a position which differs from Ci, he will see the difference of d’-1 ( which is odd ) so he will go with the color mentioned in the representative string and thus guesses it wrong.

it is easy to see that if the distance of S is indeed odd, all of them will get it right.

Cool trick, isn’t it? Well, the solution I thought it by myself, with the hint given by Ramprasad.

Related posts : here, here, here and here

— Saurabh Joshi

### Minimum Spanning Tree

December 7, 2010

Well,

The other day I came across this problem and ramprasad gave a brilliant solution to it.

Problem : Given a connected weighted graph G, find a minimum spanning tree. But wait, before you jump to any conclusion. The weights of the edges are not real numbers, but a quadratic function of time. So given a time interval [t1,t2] find out the minimum spanning tree T. That is T attains the minimum at time tm.  $\forall t \in [t1,t2], \forall TR \in {Spanning Tree of G}, W(T_{tm}) \leq W(TR_t)$. Now, find out the minimum spanning tree and the time instant tm at which it attains that minimum value.

Solution : Well, the first solution that popped up in my mind was a brute force approach. Consider all spanning trees. As the weights of edges are quadratic functions, the weights of spanning trees would also be quadratic functions. Now differentiate these functions to find the minima. Now find out the absolute minimum of all these. But apparently, the number of spanning tree of a graph could be as high as $n^{n-1}$  thanks to Kirchoff. So obviously, it does not fit into our perception of “efficient algorithm”.

Ramprasad gave a nice solution which is definitely polynomial time. Not sure whether there are better solutions or not. Note that, prim’s algorithm or kruskal’s algorithm takes into account the order of weights of edge and does not really care about what these actual weights are.  So as long as the order of the weights remains unchanged, you can apply one of these algorithm. Given the time interval [t1,t2] it can give rise to infinitely many instances of the weighted graph. As the weight function of edges are quadratic ( parabola ) there are at most $O({|E| \choose 2})$ many intersection points. That is, parabola corresponding to two edges intersect at atmost 2 points.  And these intersection points are the points in time where weight of one edge goes beyond the weight of another edge.

So, sort these intersection points by time co-ordinate. Note, that between two consecutive intersection points, the order of the weights remain unchanged and hence one of the standard algorithm can be applied. So we need to run Prim’s or Kruskal’s algorithm ($O(|E| log |V|))$for each such interval giving rise to $O(|E|^3 log |V|)$ algorithm overall. Clearly, a major improvement over the brute force method.

### Shortest Path

December 3, 2010

Hi,

I am sure most of you must be aware of dijkstra’s shortest path algorithm. Now here is a bit interesting version of it.

Problem : You are given a weighted connected graph with all edges having positive weights. Some of the cities ( nodes ) have petrol pump whereas some don’t. You have a car with the tank capacity of C. That is, with full tank, the car can travel for C units of distance. At any city with the petrol pump the car can fill its tank to full. Find out the shortest distance from a given source vertex to a given destination vertex with these constraints. Find out the shortest path between the given source and destination. Find out the shortest paths and distances from the source to all vertices.

Solution : Actually, this time, I am being a bit lazy. But I have this simple idea which certainly is a solution. Probably with a scope to improve it. Given the graph, take a vertex v without a petrol pump.  Remove this vertex and all edges incident on it. Now, for all neighbours u1,..,uk of it, add/update edges between (ui,uj). These edges can now store the shortest path between (ui,uj). Once the graph is converted in this manner, the standard algorithm can be applied. The conversion of this graph can be done in $O(n^3)$ or $O(n^4)$ depending upon whether we need the paths or just distances. I know I have omitted many details. But all in all, this trick can give rise to a $O(n^4)$ algorithm ( probably $O(n^3)$ not sure 😉 ) which does the job. Let me know if you can do better 🙂

### Secret Sharing-3

November 26, 2010

As promised in the last post,  I am back with the solutions to the problem we left. There are  couple of solutions when collection of sets is given explicitly. If for example, sets S1 to Sn are given with the constraint that all and only members together from any set should be able to unlock the secret. Given n such sets, there are two solution which are similar in some sense.

First solution, can make the unlocking as hard as possible. That is, there is a brute force way to unlock, even if you are not authorized. In this, we share a secret as n tuple, each co-ordinate in the tuple is of length 1024 ( making it $2^{1024}$ possibilities ). That is for each set, you have 1024 bit. Choose a secret S and make n copies of it. Now, for each element of the tuple ( that is for each set Si) you can use the XOR method that we mentioned in the first post of the series.

Second solution, again uses tuples, but instead of using the XOR one can use the polynomials. Choose, different polynomial for each co-ordinate of the tuple such that the polynomial constant is secret S. This is again described in the first post.
However, when sets are not given explicitly, the size of the tuple becomes very large if one goes on to enumerate all possible sets which can unlock. The solution which ramprasad had in mind is using circuit with threshold gates. $Th_k$ is a k-threshold gate which becomes one when k or more of the inputs are set to one.

Now, let us see how the circuit for the counter example mentioned in the last post would look like.

The example was as follows. group of 8 persons. 5 or more should be able to unlock the secret. If there are 4, then they would be able to unlock only if there are even of them from the first half ( in turn, there are even of them from each half 🙂 ).

The circuit would look like this

$Th_5 \;OR\; (LTh_4)\; OR\; (LTh_2\; AND\; RTh_2)\; OR\; (RTh_4)$ where LTh and RTh denotes threshold gates for the left and the right half. Note that if we want to enumerate the sets there are ${8 \choose 5} + {4 \choose 2}{4 \choose 2} + 2{4 \choose 1}$ sets. In comparision, having such a circuit is a very efficient solution 🙂

### Secret Sharing – 2

November 25, 2010

Well,

We have already talked about secret sharing in one of the earlier post. Funny thing happened recently, Ramprasad came up with a question which is a little bit modified. He had a different answer in mind, but I came up with a very simple solution.

Problem : Given a secret S, you have to divide it amongst $p1,\dots,p6$ such that p1 and p2 together should unlock the secret. Alternatively, p1 or p2 along with three of the other four ( p2 to p6 ) should be able to unlock the secret. However, p2 to p6 together should not be able to unlock the secret.

Solution : I came up with a very simple solution. Take any random polynomial of degree 5 such that the constant term is our secret. Evaluate this polynomial at 10 nonzero random points. Now, give 3 points each to p1 and p2 along with their values. Similarly, distribute one point each to the remaining four persons. See that to construct the original polynomial and hence evaluate it at zero, you need at least 6 points.

For this concrete example this solution is perfectly valid. I was tempted to generalize it as follows.

Let us say that we are given collection of sets. In this case, sets are {1,2},{1,3,4,5},{1,3,4,6} ….. and so on. Meaning, you should be able to unlock the secret when all the members of any set are present. I was tempted to generalize the solution I gave earlier, as follows.

Write it in form of constraints such that we will give each person pi weight wi

So now the constraints will be

$\forall i w_i > 0$ ( we will give some positive number of points of polynomials to each of them )

$\forall _{S_i \in C} \sum _{j \in S_i} w_j \geq 1$ ( when all members of any set is present it should unlock the secret ( threshold is 1 )

$\forall _{S_i \in C} \forall _{x \in S_i} \sum _{j \in S_i - x} w_j < 1$ ( if not all members of the set are present, they should not be able to unlock the secret )

The reason why threshold is taken as 1 is because once we get any feasible solution to this system of inequalities, we can always scale it up, so that all $w_i$ are positive integers and accordingly we will choose threshold T  ( degree T-1 polynomial ). So when collectively when they have T points, they can construct the polynomial and hence, can unlock the secret.

How do we know that the system of inequalities always have the solution? ( if it does, it has infinitely many of them ). Apparently, it is not always possible to have the solution for such a system. Here, any solution defines a hyperplane in n-dimension ( n being total number of people ) such that all the points above it are acceptable and all the points below it are not.

So for collection of sets which demands non-linear surface, this method will not work. Here is a counter-example that ramprasad came up with.

Let us say that there ar 8 persons. You are supposed to divide the secret in the following manner.

1. If there are 5 or more together, they can unlock
2. If there  are exactly 4 of them, then if there are even number of them from the first half ( p1 to p4 ) then they should be able to unlock the secret.
3. Should not be able to unlock in all other cases.

Observe that this gives rise to non-linear partitioning surface.

There are many different generic solution  to this kind of problem. Will talk about it sometime later 🙂

### Circles and Tangents

November 23, 2010

Recently I came across a very nice puzzle related to geometry.

Problem : Take any three non-intersecting circles of distinct radii. Common tangents of any two will intersect at a point. Prove that the three intersection points due to three pairs of tangents are co-linear.

Solution : Ramprasad and I came up with a proof but we believe that there should be much simple and elegant proof. If you can throw any light, please comment. Here is the proof.

Let the center of circles A, B and C be denoted by $C_A, C_B,C_C$. Also the intersection points be denoted by $X_{AB}, X_{BC}, X_{AC}$ and radii are $r_A,r_B,r_C$.

Given any two circles, say A and B. Following relation holds due to congruence of the triangles formed.

$\frac{X_{AB}C_{A}}{X_{AB}C_B} = \frac { r_A} { r_B}$. Now, $X_{AB}C_{A} = X_{AB}C_B + C_B C_A$

Simplifying, we will get $X_{AB}C_A = \frac{r_A}{r_A-r_B}C_AC_B$. Thus, we have got how far a point will be given the radii of two circles and the distance between their centers. Let $\alpha_{AB} = \frac{r_A}{r_A-r_B}C_AC_B$.

Now, Let $C_A$ be the origin and with respect to that the vectors of $C_B,C_C$ be denoted as $v_B,v_C$.

So, vector $v_{XAB}$ for $X_{AB}$ will be $\alpha_{AB}v_B$.

Similarly, $v_{XAC} = \alpha_{AC}v_C$ and $v_{XBC} = \alpha_{BC}(v_C-v_B) + v_B = ( 1 - \alpha_{BC})v_B + \alpha_{BC}v_C$

For three points to be collinear, following must hold for some $\lambda$.

$v_{XBC} = \lambda v_{XAB} + ( 1 - \lambda ) v_{XAC}$

Therefore, we must prove that for some $\lambda$

$( 1 - \alpha_{BC})v_B + \alpha_{BC}v_C = \lambda \alpha_{AB}v_B + ( 1 - \lambda) \alpha_{AC}v_C$
Simplifying,

$\lambda=\frac{ 1- \alpha_{BC} }{ \alpha_{AB} }$ and $\lambda = 1 - \frac{\alpha_{BC} }{\alpha_{AC} }$

You can verify that it is indeed the case that

$\frac{ 1- \alpha_{BC} }{ \alpha_{AB} } = 1 - \frac{\alpha_{BC} }{\alpha_{AC} }$

Very ugly math, and with very high probability I must have made a typo in the calculation. Please try it yourself and convince that the property holds. I am looking for a better proof!

### Logic and games -2

November 20, 2010

Well,

In the earlier post I mentioned about using games as a mean to prove/disprove expressibility of FO ( First Order Logic ).

Let us modify the game that we saw last time. Now each round consists of the following : The spoiler chooses one of the structure, chooses a subset of elements of that structure, duplicator has to do the same on the other structure. Now, the spoiler puts a pebble on one of the elements of the subset he/she has chosen and duplicator replies by playing it on the other structure. We have seen in the earlier post that it is impossible to distinguish between two graph A (two disconnected 5-cycle )and B ( one 10-cycle ) using only 3 pebbles. In fact, you will need log 2k pebbles to distinguish between two disconnected k-cycles and one 2k-cycle.

However, in this modified game, only 3 pebble suffices for the spoiler to win for any k. Here is the strategy for the spoiler to expose the difference between two structure.

Look at the figure. Spoiler first chooses one of the k-cycle in A and puts a pebble. Duplicator selects k-points in B ( 2k-cycle ) and puts a pebble. Now, the spoiler chooses the second k-cycle and puts a pebble and duplicator replies. For the third round, the spoiler chooses to play on B. It selects the shortest path between two fixed pebbles as subset, and puts a pebble right in the middle of it. Duplicator now has to play it in A ( two disconnected k-cycles ). Now, according to pigeonhole principle one of the k-cycle will have two pebbles. As shown in figure, (1,2) and (2,3) are in different cycles. Now on, spoiler will always play in graph B. it will choose a pair of pebbles belonging to different cycles in A, selects the pair having shortest path in graph B and puts the pebble right in the middle of it. The spoiler always maintain that it divides the path between pebbles images of which are in different cycles in the other graph. it is easy to see that, after some time, duplicator will have no answer to spoiler’s move ( isomorphism implied by pebbles can not be maintained in the other graph ).

This game gives rise to a logic which is strictly powerful than FO. However, Ramprasad mentions that due to a recent result one can always construct pairs of graphs that spoiler can not win for any k-pebble game. Also, this game has some connection to graph isomorphism but probably ramprasad will give details in the comment 😉

Similar games are designed to prove/disprove the expressibility of temporal logic, but may be some other time 🙂

— Saurabh Joshi