A Simple Bijection between Even and Odd Subsets

Let $E(n)$ denote the set of even subsets (subsets of even size) and $O(n)$ the set of odd subsets (subsets of odd size) of a set $S$ containing $n$ elements.  Assuming $n \geq 1$, we can describe a simple bijection between these two sets as follows-

Let $y$ be any arbitrary element of the set $S$. Then, we simply map each $A \subseteq S$ to the set $A \triangle \{y\}$, the symmetric difference of the subset $A$ and the singleton set $\{y\}$. In other words, if the set $A$ does not contain the element $y$, then we map it to the set $A \cup \{y\}$; otherwise, if $A$ already includes the element $y$, then we map it to the set $A \setminus \{y\}$.

Under this mapping, since each subset gets mapped to a subset whose cardinality is either 1 more or 1 less than its own cardinality, its easy to see that odd subsets get mapped to even subsets while even subsets get mapped to odd subsets. Moreover, since $|E(n)| = |O(n)|$ and the mapping is one-to-one, it has to be a bijection.  

An Irrational Raised to the Power of an Irrational - Can it be Rational?

If you like playing around with numbers, here is a question for you to ponder over: is it possible to obtain a rational number by raising an irrational number to the power of another irrational number?

The answer, rather surprisingly, is YES. 

And here is a classic proof to establish the fact beyond all doubt -

Let us consider the irrational numbers $\sqrt{2}$ and $\sqrt{3}$.

Now, let us look at the number $\sqrt{3}^{\sqrt{2}}$, which is obtained by raising an irrational number to the power of another irrational number.

If the number $\sqrt{3}^{\sqrt{2}}$ is rational, then we are already successful in proving our claim.

Otherwise, if $\sqrt{3}^{\sqrt{2}}$ is irrational, then let us look at the number $(\sqrt{3}^{\sqrt{2}})^{\sqrt{2}}$, which is again obtained by raising an irrational number to the power of another irrational number.

However, $(\sqrt{3}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{3}^{(\sqrt{2}.\sqrt{2})} = (\sqrt{3})^{2} = 3$, which is a rational number. Thus, in this case also, our claim is proven. 

Hence, in either case, we have managed to establish that it is indeed possible to obtain a rational number by raising an irrational number to the power of another irrational number.


Notice that the above proof, attributed to Dov Jarden, is non-constructive in nature, which means that it does not provide us explicitly with a rational number obtained by raising an irrational to the power of another. However, in case you are someone who doesn't feel satisfied without seeing an explicit example, consider the number $(\sqrt{3})^{\log_{3}{4}}$.

We know that $\sqrt{3}$ is irrational. Let us convince ourselves that $\log_{3}{4}$ is also irrational.
Suppose it was rational. Then, we could have written it in the form $\frac{p}{q}$, where $p$ and $q$ are co-prime integers. In that case, we would have had:
$$ \log_{3}{4} = \frac{p}{q} \Leftrightarrow 3^{\frac{p}{q}} = 4 \Leftrightarrow 3^{p} = 4^{q} $$
which is clearly a contradiction, since $3^p$ is odd while $4^q$ is even. Hence, the number $\log_{3}{4}$ must be irrational.
Now, $(\sqrt{3})^{\log_{3}{4}} = 3^{\frac{1}{2}\log_{3}{4}} = 3^{\log_{3}{2}} = 2$, which is rational. Thus, it is further proof that our assertion is indeed correct.

Product of k Consecutive Numbers is Divisible by k!

Suppose $P$ is the product of $k$ consecutive integers, where $k \geq 1$.
Then, $k!$ divides $P$ .


Proof 1 -

Let $P$ be the product of $k$ consecutive integers from $n+1$ up to $n+k$, so that we have:

$$ P = (n+1)(n+2)...(n+k) = \frac{(n+k)!}{n!} $$

Now, we know that the power of any prime $p$ in $k!$ is given by the following finite sum:

$$ \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{k}{p^m} \right\rfloor} $$

Therefore, the power of any prime $p$ in the product $P$ is given by:

$$ \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n+k}{p^m} \right\rfloor}
- \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n}{p^m} \right\rfloor} $$
Since $ \forall p,q,r \in \mathbb{Z}^{+}: \left\lfloor \frac{p+q}{r} \right\rfloor \geq
\left\lfloor \frac{p}{r} \right\rfloor + \left\lfloor \frac{q}{r} \right\rfloor $, we must have:

$$ \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n+k}{p^m} \right\rfloor}
- \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{n}{p^m} \right\rfloor}
\geq \sum\limits_{m \geq 1}^{}{\left\lfloor \frac{k}{p^m} \right\rfloor} $$

Thus, we see that, for every prime $p$, the power of $p$ in $k!$ never exceeds the power of $p$ in the product $P$. Hence, $k!$ always divides the product $P$.

Proof 2 -

Let $P$ be the product of $k$ consecutive integers from $n+1$ up to $n+k$. So, we have:
$ \begin{aligned}
\hspace{4cm} P & = (n+1)(n+2)...(n+k) \\
& = \frac{(n+k)!}{n!} \\
& = k!  \frac{(n+k)!}{n!k!} \\
& = k!  \binom{n+k}{k}
\end{aligned} $

Now, the binomial co-efficient $\binom{n+k}{k}$, being the number of ways in which one can choose $k$ items out of a total of $n+k$ distinct items, is known to be integral. Hence, $k!$ must divide the product $P$.

Chess Puzzle - 7

The following position below is taken from a game between the legendary Russian grandmaster Garry Kasparov, considered by many to be the greatest ever chess player in the world, and his trainer Aleksander Nikitin in Moscow in 1981.

The position above (black to move) developed after 39 moves in the game that started off with the B44 Paulsen Variation of Sicilian Defense. Analyze the position carefully and try to figure out the next move by black which would leave his opponent in a pretty hopeless position. Lets see how many of you can spot it!

Finding GCD

Today, I am sharing a little problem from number theory, which is stated as:

Let $a = 7k + 2$ and $b = 9k - 5$. Then, prove that $gcd(a,b)$ is either 1 or 53.


The solution repeatedly makes use of the fact that, if $m > n$, $ gcd(m , n) = gcd(m - n, n) $. It proceeds as follows:

$ \begin{aligned} gcd (a,b) & = gcd(7k+2,9k-5) \\ & = gcd(7k+2,2k-7) \\ & = gcd(5k+9,2k-7) \\ & = gcd(3k+16,2k-7) \\ & = gcd(k+23,2k-7) \\ & = gcd(k+23,-53) \\ & = gcd(k+23,53) \end{aligned} $

Since 53 is a prime number, either it divides $k+23$, in which case we have $gcd(a,b) =$ 53, or it does not divide $k+23$, which makes $gcd(a,b) =$ 1. Hence proved.

The identity $ gcd(m , n) = gcd(m - n, n) $ doesn't just help us solve this particular problem. It is actually the core idea behind Euclid's recursive algorithm for computing the GCD of two integers. The earliest surviving description of the Euclidean algorithm can be found in Euclid's 'Elements' (c. 300 BC), making it one of the oldest numerical algorithms still in common use.