Q: A unit square is dissected into n > 1 rectangles such that their sides are parallel to the sides of the square. Any line, parallel to a side of the square and intersecting its interior, also intersects the interior of some rectangle. Prove that in this dissection, there exists a rectangle having no point on the boundary of the square.

Let us orient the square along horizontal and vertical. A horizontal or vertical line which intersects the interior of a square but does not intersect the interior of any rectangle is called a splitting line. A rectangle having no points on the interior of a square is called an interior rectangle.
Let us assume the contrary that there exists a dissection into more than one rectangles such that there are no interior rectangles and no splitting lines. Under such assumption n > 2 otherwise they will have a common side which will form a splitting line.
Let us define an operation that combines rectangles if they have a common side.With this operation the simple dissection mentioned above reduces the number of rectangles leaving no splitting lines and no rectangles which is a contradiction. So a splitting line and interior rectangle has to exist.
Now let us denote the initial square by points ABCD so that A and B lie along the horizontal. We consider a and b as two rectangles containing the vertices A and B respectively. Rectangle a is not equal to rectangle b otherwise one of their sides provides a splitting line. So let us further assume that the height of a is less than the height of b. We can use the same argument as we will use now for the other case as well when a's height is more than that of b. We are merely picking one case to proceed with the arguments. Now if consider a rectangle c next to the lower right corner of a, then a and c can have the following two cases:
height of a is greater than that of c: Then there exists a rectangle d adjacent to both a and c such that it does not have anything common with sides AB, BC and even AD but it has a common point with CD and its left side provides a splitting line. This results in the same contradiction as earlier.
height of a is less than that of c: In this case the rectangle d will lie over a but it should not border with AD otherwise it would combine with a and the same argument as above holds.
Thus we have proved by contradiction by considering all the cases.

Q:In the coordinate plane consider the set S of all points with integer coordinates. For a
positive integer k, two distinct points A,B belonging to  S will be called k-friends if there is a point C belonging to S such that the area of the triangle ABC is equal to k. A set T is a subset of S will be called a k-clique
if every two points in T are k-friends. Find the least positive integer k for which there exists
a k-clique with more than 200 elements.
A: Let us picture this problem. We can peg one vertex of the triangle on the origin and choose the remaining points  B(u,v) and C(x,y) such that they form a triangle with an area k. These points are said to be k-friends. If we translate this triangle by a vector, it will not change the area and we will get new k-friends. There are many such translations possible before we determine their number let us look at the properties of the triangle. One such translation would be to choose a new origin such that the old-origin and new-origin are k-friends.
We know the well known formula for a triangle with one vertex at origin is half of mod(uy-vx) which is equal to k for k-friends. This is equivalent to saying  the gcd of u,v is also a divisor of 2k. In other words, two points (u,v) and (0,0) are k -friends if and only if the gcd(u,v) is a divisor of 2k. When we translate, the new point (s,t) and (u,v) are k friends if and only if the point (u-s,v-t) is a k friend of (0,0) which implies gcd(u-s, v-t) divides 2k.
Let us choose a number n that does not divide 2k The claim here is that a k-clique cannot have more than n^2 elements. This is because all points (x,y) can be divided into n^2 classes determined by the remainders that x and y leave in the division by n. If a set T has more than this many points, some two points will have to fall into the same class. This means n divides u-s and n divides v-t  and hence n divides gcd(u-s,v-t) Since n does not divide 2k therefore d does not divide 2k. Points (s,t) and (u,v) are now k-friends and the set T is not a k-clique. Our claim holds.
We can now investigate different values of n to come up with 200 elements.


#custom authentication in django
We take a short break to list the custom authentication in django:
we can do this the following ways
1) we can change the  default authentication backend
2) we can change the user model
3) we can change the permissions
4) we can change the default user

How does a JWTHelper parse ?

token_parts = token.split('.')
	if len(token_parts) >= 2:
	import base64
	header = base64.b64decode(token_parts[0])
	claims = base64.b64decode(token_parts[1])
	if len(token_parts) == 3:
	crypto = base64.b64decode(token_parts[2])

if header and header.get("alg") and header.get("enc") and header.get("iv") and header.get("typ"):
	alg = header["alg"]
	enc = header["enc"]
	iv = header["iv"]
	typ = header["typ"]

Q: For every positive integer n, determine the number of permutations (a1, a2, . . . , an) of the

set {1, 2, . . . , n} with the following property:

2(a1 + a2 + · · · + ak) is divisible by k for k = 1, 2, . . . , n.

A: For each n, let Fn be the number of permutations with the said property and call them 'nice'. For n = 1,2,3 every permutation is nice, so F1 = 1, F2 = 2, F3 = 6.

Now if we take an n > 3 and consider any nice permutation (a1, a2, ... an) of {1, 2, ... n}, then n-1 must be a divisor of the number.

We now rewrite the property for k = n-1 not in terms of a1, a2, an-1 but as the sum of 1, 2 ..n  and subtracting an. This gives us
 n(n+1) - 2an = (n+2)(n-1) + (2-an)
The last part (2 - an) must be divisible by n-1, hence it must be equal to 0, n-1 or 2n-2.
Each of these implies an is either 1 or (n+1)/2 or n

Similarly if we assume an = (n+1)/2, the permutation is nice taking k = n - 2, we get  that n-2 has  to be a divisor of
 2(a1+a2 ...+an-2) = 2((1+2+...+n)-an-an-1) = n(n+1) - (n+1)-2an-1
= (n+2)(n-2) + (3 - 2(an-1))
Since the last component has to be divisible by n-2, it is equal to 0 or n-2 or 2n-4. 0 and 2n-4 are excluded because 2 an-1 -3 is odd. The remaining possibility 2(an-1 -3 = n -2) leads to an-1 = (n+1)/2 = an which cannot be true. This eliminates (n+1)/2 as a possible value of an.

From the above two we are left with either an = 1 or an = n

If an  = n, then (a1, a2, ..., an-1) is a nice permutation of {1, 2 ... n-1}. There are Fn-1 such permutations. Attaching n to any one of them in the end, creates a nice permutation of {1, 2, .. n}

If an = 1, then a1 - 1, a2 -1, ... an-1 - 1 is a permutation of 1,2 ... n-1  It is also nice because the number resulting from the property = 2(a1 + ...+ak) - 2k which is divisible by k for k <= n -1

Here too any one of the nice permutations of Fn-1 nice permutations (b1, b2 ... bn-1) of {1,2 ...n-1} gives rise to a nice permutation of {1,2 ...n} whose last term is 1.

These observations show that there are Fn-1 nice permutations of {1,2 . ... n} exist both with the last term as 1 and the last term as n. Therefore there is a recurrence of Fn = 2 Fn-1 With the base value F3 = 6, we get the formula Fn = 3.2 ^ (n-2) for n>=3.

#puzzle
A king has ten slaves. He receives 60000 bottles of wine from a neighboring king. His advisors inform him that one of the bottles is poisoned but the rest are clean.How can the king find the poisoned bottle ? Assume the poison is highly potent and no matter the dilution will be fatal.
Answer He labels each bottle with their binary representation. Each of the ten slaves is assigned a position from 0 to 9. Each of them drinks from a bottle only when the bit corresponding to their position in set The order in which the slaves die yields the label of the poisoned bottle.

Find all positive integers n, for which the numbers in the set S = {1, 2, . . . , n} can be colored red and blue, with the following condition being satisfied: the set S × S × S contains exactly 2007 ordered triples (x, y, z) such that (i) x, y, z are of the same color and (ii) x + y + z is divisible by n.
The answer is n = 64  and n = 84.

Let the numbers 1,2, ...n be colored red and blue. They are partitioned into sets of Red and Blue and denoted by R and B respectively. The size of R = r and the size of B = n - r. The triple (x, y, z) belonging to triple S x S x S is monochromatic if x, y, and z have the same color and bichromatic otherwise.(x,y,z) is divisible if  x+y+z is divisible by n.
Here the claim is there are exactly r^2-rb+b^2 divisible monochromatic triples
For any pair (x,y) that belongs to  S x S , there exists  a unique z for the chosen x,y that belongs to S such that the triple is divisible. There are exactly n ^2 divisible triples. Moreover if the triple is bichromatic, then x, y, z are either blue or two red or vice versa. In both those cases, there is exactly one pair that belongs to the set R x B.. We assign such pair to triple (x, y, z).
Consider any pair (x,y) belonging to RxB, and denote z = z for  a given x,y. Since x != y, the triples x,y,z in any order is distinct and x,y is assigned to each of them. Each pair in RxB is assigned exactly three times.
Therefore, the number of bichromatic divisible triples is three times the number of elements in RxB and the number of monochromatic ones is n^2 - 3rb where n = r + b and can be written as r^2-rb+b^2
To find all values of n where the desired coloring is possible, we have to find all n, for which there exists a composition n = r + b and r^2 -rb + b^2 = 2007.
Solving for these two equations we get (r,b)=(51,18) or (r,b)=(51,33) and the possible values of n = 51+18=69 and n = 51+33=84.

Self-healing Troublebuster software 

When we encounter a software functionality failure or a performance issue, we troubleshoot it based on well known patterns and techniques. At the heart of these diagnosis and mitigation technique is a monitoring process and a remedial process. The monitoring process is one which we take to diagnose the health, or monitor a system based on logs and counters or get alerts/feedback from the system itself. The remedial process is one which takes corrective action based on the predetermined root causes. A set of well known causes have a corresponding resolution.  

For example, take a disk usage activity. If there is a  quota for the storage size, the activity may very well use up all the quota and software relying on the storage may  run into disk space issue. A corresponding monitoring process may alert based on the usage threshold. A suitable mitigation in this case would be to increase the storage size. 

In this practical example, much of the process mentioned is mostly manual today because they are not often encountered. However a storage provider serving the  large set of such customers may want to help automate it for their customers. So a customer can set a policy to remind theselves or a system to take the same corrective action.  

Consequently we transition from a manual process such as follows : 

 

To one that involves  

As follows: 

                                                                      

 


#geometryproblem

et P be a polygon that is convex and symmetric to some point O. Prove that for some

parallelogram R satisfying P  R we have

|R| / |P| <= sqrt(2)

where |R| and |P| denote the area of the sets R and P, respectively.
Let us draw parallelograms R1 such that the midpoints of the sides of R1 are the points on the Polygon P.
Let R2 be inner parallelogram joining the midpoints of the sides of R1
Let R3 be the smallest parallelogram bounding P that is parallel to the midpoint connectors.
R2 is a subset of R3.
An affine one-to-one maps of the plane preserves the ratios of areas of subsets of the plane. A parallelogram can be transformed to a square with an affine map.
If we take a as the side of R2 and b and c as the distances of R3 from R2,
the areas of R1, R2, R3 can be written as
|R1| = 2a^2
|R3| = (a+2b)(a+2c)
and |P| >= a^2 | 2.ab/2 + 2.ac/2 = a(a+b+c)
If we assume the contrary of the given inequality in the question and substitute the above areas, we see that we get a contradiction.
Therefore the given inequality holds.
Intuitively, we may also bound the ratio to something less than 1.5.

In the grasshopper problem, we discussed yesterday, we can now observe that the number of points = 2008 in the given set M happens to be the maximum possible value that  a grasshopper can choose not to land on. For points 1 to 2009, the grasshopper necessarily lands on a point from M.
This follows from the two facts we deduced- First the number of points from M that appear in a permutation of the m+1 th  interval is greater than or equal to two times 1005 - m  because there are two landing points by which a length d can be realized. And Second there are 2008 points in M must be greater than sum of all the points up to and including the m+1 th interval which by our greedy strategy, is m+1 times the value we computed in first. Consequently 2008 is the maximum possible value for M.
Let us now look at an alternate way to solve the problem - one based on induction.
To do this we recognize that the problem implies a strengthening of itself. Instead of saying the cardinality of M = 2008, we can assume that the intersection set of M and (0,s - a(min)) is less than or equal to n where a(min) is the minimum of the number of points a1, a2, .. .an+1,s.
Now we can prove that the grasshopper never lands on a point from M in the following way:
For n = 0, we don't have to prove anything
For n > 1, by our strategy, an+1 < an < an-1 < .. < a2 < a1
Let us call this set of all the points so far as T(n+1) instead of the all inclusive M. Also T(n+1) = s
Now we make a claim that  for some m belonging to 1 to n+1, the grasshopper is  able to do at least m jumps without landing on a point of M and in addition, after these m jumps, he has jumped over at least m points of M.
m cannot be n + 1 because the max number of points in M is n.
Therefore we call n'  = n - m the remaining number of forbidden points which can be carried out in n' + 1 jumps. we shift the origin each time to execute this. This proves the claim.
This set  of points k  from 1 to n+1 such that the grasshopper can skip all the points except  for the last by arranging his jumps can be called 'smooth'.
We know that k = 1 is smooth and evident. If we can prove that k works for largest k* = n + 1, the proof is complete.
We claim that Tk*  belongs to M and the number of points in the intersection of M with (0,Tk*) is greater than or equal to k*
If there were Tk* not belonging to M, any sequence of jumps that verifies the smoothness of k* can be extended by appending ak* + 1, which is a contradiction  to the fact that k* is maximum. The second part of the claim above follows from the fact that if the number of such points were less than k* then there exists k* - 1 instead of n, the grasshopper is able to reach Tk*1 - a1 with k* jumps of lengths without al. Therefore k*+1 is also smooth which is  a contradiction.
The third claim made now is that it is sufficient to consider the case M intersection (0, Tkmin-1)  which should have less than or equal to kmin - 1 points.
This follows from the above claim because we are using the minimum kmin. Although we don't go into the formal proof for claim 3, we can intuitively follow it from the claim 2.
Now with claim 3 and the strengthening mentioned above, we have kmin - 1  instead of n, the grasshopper is able to reach Tkmin + ar - ax by kmin jumps without landing on any point of M. From there he is able to jump to Tkmin + ar and therefore we reach a situation as in claim 1 with m = kmin + 1 which completes the proof.

A grasshopper jumps along the real axis. He starts at point 0 and makes 2009
jumps to the right with lengths 1; 2; : : : ; 2009 in an arbitrary order. Let M be a set of 2008
positive integers less than 1005 * 2009. Prove that the grasshopper can arrange his jumps in
such a way that he never lands on a point from M.

Let us make a set of landing points for the grasshopper.
We look into the case when M does not contain numbers divisible by 2009.
We fix the numbers 2009k as landing points k = 1, 2, .... 1005
Consider the open interval I-k = (2009(k-1), 2009k)
We show that we can choose exactly one point outside of M as a landing point in 1004 of these intervals such that all lengths from 1 to 2009 are realized.
By excluding one interval from the 1005, we say that 2009 will indeed appear.
And each interval is length 2009 so a number d picked form 1 to 1004 is sufficient to guarantee that 2009-d  will also be picked. therefore 1004 is enough.
We pick these points in a greedy way.
Let n-k be the number of elements that belong to the interval Ik. We order these numbers in a decreasing way, so let p1, p2 ...p1005 be a permutation of 1,2, ...1005 such that the first is greater than the second which in turn is greater than the third and so on.
We leave the first interval out saying that it doesn't have a landing point now assuming that the other intervals have a landing point with d2, ... , dm where m = 1, .. 1004.
We show that there is a point in d2 .. dm that can be implemented with a new landing point in the m+1 th interval.
We do this by assuming the contrary.There are 1004-(m-1) other lengths obstructed by the np-m+1 points of M in the m+1th interval.

Each length d can be realized by two landing points namely the previous hop and the current hop.
This means that the number of elements of M that belong to the m+1 interval are greater than twice the number of points remaining to be chosen from the 1005 and written as twice * (1005-m)

Adding up the number of elements for each of the 1005 intervals equals the sum of 2008
so we know that 2008 is greater the number of points belonging to the interval from all of the m+1 intervals. and since each of these is greater than those chosen for the m+1th interval
we say that 2008 has to be greater than m+1 times the points chosen for the m+1th interval

Together the above two facts show that 2008 is greater than m+1 times twice * (1005-m)
This is minimum only when m = 1004 but the resulting value with m = 1004 is greater than 2008 - a contradiction.
Consequently there is a point in d2 .. dm that can be iplementd with a new landing point in the m+1th interval.

We now look at the other case when M does contain a number divisible by 2009. In this case we can say there is a number for which we can take multiples but it leaves a remainder less than 2009
Also we know from above that we have a landing point between 1005 and 2008.
So there are only two ranges we need to satisfy that they have a landing point
while everything else already has been shown to have it. One of this range is r shy of the multiple of 2009 and the other is 2009-r excess of the next multiple of2009. Note that both of them form a multiple of 2009. Hence we can use a similar logic as above for these ranges as well.
Thus we cover all the cases to show the grasshopper can arrange his jumps such that he can skip all point  from M