Permutation with distinct prefix sums

For a permutation $x_1, x_2, \dots, x_{100}$ of $0, 1, 2, \dots, 99$ , define 

$$S_n = \left(\sum_{j=1}^{n} x_j\right) \mod 100$$

Is there a permutation such that $S_i \neq S_j $, for all $i \neq j$?

i.e $S_1, S_2, \dots, S_{100} $ is also a permutation of $0, 1, 2, \dots, 99$?

Scroll down for a surprising solution (edit: there is a nice and  much simpler solution in the comments)

.

.

.

.

.

.

We use the fact that $101$ is a prime! 

Since $101$ is a prime, it has a primitive root $g$ and we have that:

Given $ 1 \le m \le 100$, there is a unique $0 \le e_m \le 99$ such that $$g^{e_m} = m \mod 101$$.

Note also, that the $e_i$ are distinct $\mod 100$ because $g$ is a primitive root and $g^{x} = g^{x \mod 100} \mod 101$.

Now we make the following claim:

$\textbf{Claim:}$ The sequence $$\begin{aligned}&x_1 = e_1 = 0\\&x_2 = e_2 - e_1 \mod 100\\&x_n = e_n - e_{n-1} \mod 100\\ &x_{100} = e_{100} - e_{99} \mod 100 \end{aligned} $$ 

is a permutation that satisfies the distinct prefix sum property!

$\textbf{Proof:}$ 

First let's prove that $x_1, x_2, \dots, x_{100}$ is indeed a permutation of $0, 1, 2, \dots 99$.

Suppose it were not, then we must have that $x_i = x_j$ for some $i \neq j$. 

Note $x_1 = 0$ and we have that $e_{n} \neq e_{n-1} \mod 100$ (as the $e_i$ are distinct $\mod 100$). Thus we cannot have that $x_1 = x_i$ for $i \neq 1$. 

Now suppose $e_{i+1} - e_{i} = e_{j+1} - e_{j} \mod 100$ (with $0 < i, j \leq 99$). This implies that

$$g^{e_{i+1} - e_{i}} = g^{e_{j+1} - e_j} \mod 101$$

By definition, $g^{e_n} = n \mod 101$. Thus we must have that

$$ \dfrac{i+1}{i} = \dfrac{j+1}{j} \mod 101 \implies i = j \mod 101$$  

Thus $x_1, x_2, \dots, x_{100}$ is indeed a permutation of $0,1,2, \dots, 99$.

The prefix sums of the $x_i$ are just $S_n = e_1 + (e_2 - e_1) + \dots + (e_n - e_{n-1}) = e_n$.

Thus $$S_1, S_2, \dots, S_{100} = e_1, e_2, \dots, e_{100}$$

Since the $e_i$ are distinct $\mod 100$, the $S_i$ are distinct too, and we are done!

This is an original problem and this solution seems like overkill (but pretty nice if I may say so myself). If you find a simpler solution, please post in the comments.

MoMath Mindbender: 10 points and unit circles

 Another nice puzzle from Peter Winkler on the momath website.

The puzzle: Given $10$ points on the 2D plane, can you cover them all with disjoint unit circles? i.e. Can you find a set of disjoint unit circles such that each of the $10$ points lie inside the circles?

.

.

.

.

Solution:

We give a probabilistic proof!

First consider that if we were asked to use a regular hexagon of side $s$ instead (and allowing them to touch only at the sides instead of full disjointedness), we could do it easily because we can tile the plane with a regular hexagon of any given size. We just tile the plane with regular hexagons of side $s$, translating/rotating etc if points happen to lie on the hexagon sides. 

Now consider a regular hexagon, so that the radius of the inscribed circle inside the hexagon touching all its sides is $1$. The ratio of area of the circle to that of the hexagon comes out to be $\dfrac{\pi}{2\sqrt{3}} \approx 0.906 > 0.9$. 

So basically the hexagon is a "good approximation" for the unit circle and we could try to use hexagons instead, hoping none of the points lie in the areas outside the unit circle. Now could translating etc work if a point happens to lie inside the unwanted area of the hexagon, that is not part of the circle?

This is where we can use the probabilistic method. 

We are given the $10$ points. We now randomly tile the plane with regular hexagons whose inscribed circle is of radius slightly $ > 1$.  We do this so that the unit circles centered at the centers of the hexagons can be disjoint. We can choose the side length so that the probability that any given point strictly lies inside the unit circle is still $\approx 0.906$. 

Note that events are not independent (because the relative locations of the points are fixed), but by linearity of expectation, the expected number of points that lie strictly within the unit circles is $10 \times 0.906 > 9$. Thus there has to be some random arrangement of the hexagons where all the $10$ points lie inside the unit circles!

Primitive Pythagorean triples with the help of trigonometry

 Not a puzzle, just a quick note.

Primitive pythagorean triples are of the form $m^2 - n^2, 2mn, m^2 + n^2$ with $m,n$ relatively prime and of opposite parities.

We will use trigonometry to help derive this.

Let $a,b,c$ with $a^2 + b^2 = c^2$ be a primitive pythagorean triplet. This means $\gcd(a,b,c) = 1$. Note that this also implies that $a,b,c$ are pairwise coprime. Thus exactly one of $a,b,c$ is even. It cannot be $c$ as that would imply $4$ divides $a^2 + b^2$ for $a,b$ odd (which is not possible). 

Thus assume $b$ is even. 

We can now prove that 

$\textbf{Proposition:}$ With $b$ even, the highest power of $2$ that divides $b$ is different from the highest power of $2$ that divides $a+c$. 

$\textbf{Proof:}$ Since $a,c$ are odd and relatively prime, we must have that $\gcd(a+c, c-a) = 2$. Thus $a+c = 2u$ and $c-a = 2v$ for some odd $u,v$. Now if $b = 2w$ for some odd $w$ (if we assume that the highest power of $2$ that divides $b$ is same as $a+c$), then $b^2 = (c+a)(c-a) \implies w^2 = uv$. Since $w^2 = 1 \mod 4$, this implies $u = v$ mod $4$, and thus $a = u - v = 0 \mod 4$, not possible.

Now consider the triangle $$B = (0,0), C = (a, 0), A = (a,b)$$

Draw the anglular bisector $BD$ of angle $B$ such that $D$ lies on $AC$. By the angular bisector theorem, $CD/DA = a/c$ and hence $CD = \frac{ab}{a+c}$. Thus we have that

$$\tan \left(\frac{B}{2}\right) = \frac{CD}{BC} = \frac{b}{a+c} = \frac{n}{m}$$

For some $n, m$ relatively prime.  Since the highest power of $2$ that divides $b$ is different from that of $a+c$, $n,m$ are of opposite parities.

Now using $\tan 2x = \frac{2 \tan x}{1 - \tan^2 x}$ we get

$$\frac{b}{a} = \tan B = \frac{2 n/m}{1 - (n/m)^2} = \frac{2nm}{m^2 - n^2}$$

We can show that $2mn$ and $m^2 -n^2$ are relatively prime if $m,n$ are relatively prime and of opposite parities: if a prime $p > 2$ divides the numerator, it has to divide one of $m,n$ and cannot divide the denominator also. The denominator is also odd, so their $\gcd$ cannot be $2$.

Thus $$b = 2mn, a = m^2 - n^2, c = m^2 + n^2$$

Limit of sum of first $n^{th}$ powers.

 Came across this problem recently, posed as apparently an IIT JEE exam question (though I haven't been able to find the exact year). This is a horrible question for the exam (which is usually multiple choice with negative marking) because it rewards bad students and punishes the good students. And as expected, the IIT JEE coaching class solution I found for this was utterly wrong. A sad state of affairs.

Here is the gist of the question (the actual question was a bit different, but this is the crux of the question).

Find $$\lim_{n \to \infty} \dfrac{1^n + 2^n + \dots + n^n}{n^n}$$

The wrong solution goes as follow

$$\lim \sum_{j=1}^{n} \left(\dfrac{j}{n}\right)^n = \lim \sum_{k=0}^{n-1} \left(\dfrac{n-k}{n}\right)^n$$

$$ = \lim \sum_{k=0}^{n-1} \left(1 - \dfrac{k}{n}\right)^n = \lim \sum_{k=0}^{n-1} e^{-k} = \dfrac{e}{1-e}$$

The step going to $e^{-k}$ is wrong, without some additional justification. In fact, it can be justified using theorems (like monotone/dominated convergence theorems) which is not in the syllabus of IIT JEE. A good student who does not know those theorems will likely be stuck, while a bad student will happily get the right answer by using pretty faulty reasoning.

Below is an attempt to prove that the limit is $\dfrac{e}{e-1}$ using "elementary" means.

The steps are similar till

$$  \dfrac{1^n + 2^n + \dots + n^n}{n^n} = \sum_{k=0}^{n-1} \left(1 - \dfrac{k}{n}\right)^n$$

At this point we try to give upper and lower bounds which ultimately give us the limit we seek,

We use $e^{x} \ge 1 + x$ multiple times. 

Setting $x = \frac{-k}{n}$ gives us $e^{-k/n} \ge (1 - k/n)$ and thus $$ \left(1 - \dfrac{k}{n}\right)^n \le e^{-k}$$

Setting $x = \frac{t}{1-t}$ gives us $e^{t/(1-t)} \ge \frac{1}{1-t}$, and so $e^{t} \ge (1-t)^{t-1}$ and thus $(1-t)^{1-t} \ge e^{-t}$

Setting $t = \frac{k}{n}$ and rearranging gives us

$$\left(1 - \dfrac{k}{n}\right)^n \ge \left(1 - \dfrac{k}{n}\right)^k e^{-k}$$

By Bernouli's inequality $\left(1 - \dfrac{k}{n}\right)^k \ge \left(1 - \dfrac{k^2}{n}\right)$ and so we have the bounds

$$e^{-k} \ge \left(1 - \dfrac{k}{n}\right)^n \ge \left(1 - \dfrac{k^2}{n}\right) e^{-k}$$

Taking the sum from $k = 0$ to $n-1$, and noticing that $\sum k^2 e^{-k}$ is $O(1)$ and hence $\frac{1}{n}\sum k^2e^{-k} \to 0$ as $n \to \infty$ gives us the result.