How to deal with failure?

Standard

If you are an average student (like me…) and are part of an insane curriculum (like having 5 advanced math courses in one semester) you may fail in few of your courses at college, even after trying your best to pass them.  In such situations you may be able to control your panic by reading this Reddit post:

I will suggest you to go through the comments of that post.

Nim

Standard

Nim is a very old game with precise mathematical theory, and one player can always force a win.

The game is Nim is played as follows: Any number of matches/pebbles are arranged in heaps, the number of heaps and the number matches/pebbles in each heap, being arbitrary.  There are two players, A and B. The first player A takes any number of matches/pebbles from a heap, he/she may take only one or any number up to the whole of the heap, but he/she must touch one heap only. B then makes a move conditioned similarly, and the players continue to take alternate turns of picking matches/pebbles. The player who takes the last match/pebble wins the game.

We define a winning position as a position such that if one player P (A or B) can secure it by his/her move, leaving his/her opponent Q (B or A) to move next, then, whatever Q may do, P can play so as to win the game. Any other position we call a losing position.

Next, we express the number of matches in each heap in the binary scale and form a figure by writing down one under the other. Then we add up the columns. For example, consider the following position:

Then, (1,3,5,7) position gives the following figure:

001
011
101
111

224

If the sum of each column is even (which is the case above), then the position is correct. An incorrect position is one which is not correct, thus (1,3,4) is incorrect.

Then we have the following result:

A position in Nim is a winning position if and only if it is correct.

For the proof/discussion/variations of rules, see § 9.8, of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers.

But designing an elaborate winning strategy, i.e. ensuring that you always stay in winning position, is not so easy (though we know it exists!). For example, watch this video by Matt Parker:

Finite Sum & Divisibility – 2

Standard

Earlier this year I discussed a finite analogue of the harmonic sum. Today I wish to discuss a simple fact about finite harmonic sums.

If $p$ is a prime integer, the numerator of the fraction $1+\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{p-1}$ is divisible by $p$.

We wish to treat the given finite sum modulo $p$, hence we can’t just add up fractions. We will have to consider each fraction as inverse of an integer modulo p. Observe that for $0, we have inverse of each element $i$ in the multiplicative group $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$, i.e. there exist an $i^{-1}$ such that $i\cdot i^{-1}\equiv 1 \pmod p$.

For example, for $p=5$, we have $1^{-1}=1, 2^{-1}=3, 3^{-1}=2$ and $4^{-1}=4$.

Hence we have
$\displaystyle{i\cdot \frac{1}{i}\equiv 1 \pmod p ,\qquad (p-i)\cdot \frac{1}{p-i} \equiv 1 \pmod p }$
for all $0.

Hence we have:
$\displaystyle{i\left(\frac{1}{i}+\frac{1}{p-i}\right)\equiv i\cdot \frac{1}{i} - (p-i)\cdot \frac{1}{p-i} \equiv 0 \pmod p}$

Thus we have:
$\displaystyle{\frac{1}{i}+\frac{1}{p-i}\equiv 0 \pmod p}$

The desired result follows by summation.

We can, in fact, prove that the above harmonic sum is divisible by $p^2$, see section 7.8 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers for the proof.

Farey Dissection

Standard

The Farey sequence $\mathcal{F}_n$ of order $n$ is the ascending sequence of irreducible fractions between 0 and 1, whose denominators do not exceed $n$. This sequence was discovered by Charles Haros in 1806, but Augustin-Louis Cauchy named it after geologist John Farey.

Thus $\frac{h}{k}$ belongs to $\mathcal{F}_n$ if $0\leq h\leq k\leq n$ and $\text{gcd}(h,k)=1$, the numbers 0 and 1 are included in the forms $\frac{0}{1}$ and $\frac{1}{1}$. For example,
$\displaystyle{\mathcal{F}_5 = \frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}}$

Following are the  characteristic properties of Farey sequence (for proofs refer §3.3, §3.4 and §3.7 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers):

1. If $\displaystyle{\frac{h}{k}}$ and $\displaystyle{\frac{h'}{k'}}$ are two successive terms of $\mathcal{F}_n$, then $kh'-hk'=1$.
2. If $\displaystyle{\frac{h}{k}}$$\displaystyle{\frac{h''}{k''}}$ and $\displaystyle{\frac{h'}{k'}}$ are three successive terms of $\mathcal{F}_n$, then $\displaystyle{\frac{h''}{k''}=\frac{h+h'}{k+k'}}$.
3. If $\displaystyle{\frac{h}{k}}$ and $\displaystyle{\frac{h'}{k'}}$ are two successive terms of $\mathcal{F}_n$, then the mediant $\displaystyle{\frac{h+h'}{k+k'}}$ of $\displaystyle{\frac{h}{k}}$ and $\displaystyle{\frac{h'}{k'}}$ falls in the interval $\displaystyle{\left(\frac{h}{k},\frac{h'}{k'}\right)}$.
4. If $n>1$, then no two successive terms of $\mathcal{F}_n$ have the same denominator.

The Stern-Brocot tree, which we saw earlier while understanding the working of clocks, is a data structure showing how the sequence is built up from 0 (=0/1) and 1 (=1/1) by taking successive mediants.

Now, consider a circle $\mathcal{C}$ of unit circumference, and an arbitrary point $O$ of the circumference as the representative of 0 (zero), and represent a real number $x$ by the point $P_x$ whose distance from $O$, measured round the circumference in the anti-clockwise direction, is $x$.

Plainly all integers are represented by the same point $O$, and numbers which differ by an integer have the same representative point.

Now we will divide the circumference of the circle $\mathcal{C}$ in the following manner:

1. We take the Farey sequence $\mathcal{F}_n$, and form all the mediants $\displaystyle{\theta = \frac{h+h'}{k+k'}}$ of the successive pairs $\displaystyle{\frac{h}{k}}$$\displaystyle{\frac{h'}{k'}}$. The first and last mediants are $\displaystyle{\frac{1}{n+1}}$ and $\displaystyle{\frac{n}{n+1}}$. The mediants naturally do not belong themselves to $\mathcal{F}_n$.
2. We now represent each mediant $\theta$ by the point $P_\theta$. The circle is thus divided up into arcs which we call Farey arcs, each bounded by two points $P_\theta$ and containing  one Farey point, the representative of a term of $\mathcal{F}_n$. Thus $\displaystyle{\left(\frac{n}{n+1},\frac{1}{n+1}\right)}$ is a Farey arc containing the one Farey point $O$.

The aggregate of Farey arcs is called Farey dissection of the circle. For example, the sequence of mediants for $n=5$, say $\mathcal{M}_5$ is
$\displaystyle{\mathcal{M}_5 = \frac{1}{6},\frac{2}{9},\frac{2}{7},\frac{3}{8},\frac{3}{7},\frac{4}{7},\frac{5}{8},\frac{5}{7},\frac{7}{9},\frac{5}{6}}$

And hence the Farey disscetion looks like:

Let $n>1$. If $P_{h/k}$ is a Farey point, and$\frac{h_1}{k_1}$, $\frac{h_2}{k_2}$ are the terms of $\mathcal{F}_n$ which precede and follow $\frac{h}{k}$, then the Farey arc around $P_{h/k}$ is composed of two parts, whose lengths are
$\displaystyle{\frac{h}{k}-\frac{h+h_1}{k+k_1}=\frac{1}{k+k_1}, \qquad \frac{h+h_2}{k+k_2}-\frac{h}{k}=\frac{1}{k(k+k_2)}}$
respectively. Now $k+k_1<2n$, since $k_1$ and $k_2$ are unequal (using the point (4.) stated above)and neither exceeds $n$; and $k+k_1>n$ (using the point (3.) stated above). We thus obtain:

Theorem: In the Farey dissection of order $n$, there $n>1$, each part of the arc which contains the representative $\displaystyle{\frac{h}{k}}$ has a length between $\displaystyle{\frac{1}{k(2n-1)}}$ and $\displaystyle{\frac{1}{k(n+1)}}$.

For example, for $\mathcal{F}_5$ we have:

Using the above result, one can prove the following result about rational approximations (for more discussion, see §6.2 of  Niven-Zuckerman-Montgomery’s An Introduction to the Theory of Numbers):

Theorem: If $x$ is a real number, and $n$ a positive integer, then there is an irriducible fraction $\displaystyle{\frac{h}{k}}$ such that $0 and $\displaystyle{\left| x-\frac{h}{k}\right| \leq \frac{1}{k(n+1)}}$

One can construct a geometric proof of Kronceker’s theorem in one dimension using this concept of Farey dissection. See §23.2 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers  for details.