Periodicity of integer parts of n!/e.

Follow up of the previous puzzle.

Let $M$ be a given positive integer $ > 1$. Let $$S_n = \left\lfloor \frac{n!}{e} \right\rfloor$$

Show that sequence $S_0, S_1, S_2, \dots$ is periodic $\mod M$ with period $2M$.

i.e show that $S_{n+2M} = S_n \mod M$

Scroll down for a solution.

.

.

.

.

Based on the previous puzzle solution, we have that

$$S_n = n! \sum_{k=1}^{m} \frac{2k}{(2k+1)!}$$

where $2m+1$ is the largest odd number $\leq n$.

From this, we can easily derive the following recurrence

$$\begin{aligned}& S_{2n+1} = (2n+1) S_{2n} + 2n \\& S_{2n} = 2n S_{2n-1} \end{aligned}$$

First notice that for any $k \ge 0$,  $S_{2kM} = 2kM S_{2M-1} = 0 \mod M$.

Now an induction like argument (on $(k,r)$) shows that $S_{2kM + r} \mod M$ is independent of $k$ and thus $S_n \mod M$ is periodic with period $2M$

Starting Decimal Digits of Integer Square Roots

 Here is a cute result.

Given a finite string of digits $S = a_1 \dots a_k$, show that there is a positive integer $N$ such that the fractional part of $\sqrt{N}$ is of the form $0.S... = 0.a_1 \dots a_k \dots$.

For eg, is $S = "414"$, we have that $\sqrt{2} = 1.414\dots$ and fractional part is $0.414\dots$.

Scroll down for a solution.

.

.

.

.

.

Given $S = a_1 \dots ...a_k$, treat it as the number $M = a_1 a_2\dots a_k$.

We can also assume $a_k < 9$ (otherwise, we can just extend $S$ by the digit $0$).

Now consider $X = 10^{2k} + M$.

There are $2X+1$ numbers between $X^2$ and $(X+1)^2$ (not including $(X+1)^2$). Since $X \ge 10^{2k}$, some number among those is divisible by $10^{2k}$. Say it is $P = 10^{2k} Q$.

We have that

$$X^2 \leq 10^{2k}Q < (X+1)^2$$

which implies

$$ X \leq 10^k \sqrt{Q} < (X + 1)$$

i.e

$$ 10^k + \frac{M}{10^k} \leq \sqrt{Q} < 10^{k} + \frac{M + 1}{10^k}$$

And thus $Q$ is the required number.

For eg for $S = 2026$, we get $Q = 100004053$ and $\sqrt{Q} = 10000.2026479\dots$.

Oddness of Binomial Coefficients

 There are well known theorems like Lucas' or Kummer's which allow one to figure out exactly which binomial coefficients $\binom{n}{k}$ are odd.

The goal of this (slightly open ended) puzzle is to not use these theorems and still come up with a characterization of the $n,k$ for which $\binom{n}{k}$ is an odd number.

Scroll down for one simple "elementary" way.

.

.

.

.

.

We prove the following:

$\textbf{Claim:}$ Given an $n = \sum 2^{e_i}, e_i \text{ distinct} $ , then we have that $\binom{n}{k}$ is odd iff $k$ is the sum of some subset of the $2^{e_i}$. i.e $k$ is written only using the "set" bits of $n$. The empty set corresponds to $k = 0$.

$\textbf{Proof:}$

Consider polynomials where the coefficients are either $0$ (for even) or $1$ for odd, with the rule that $1 + 1 = 0$.

So we have $1 - 777x$ being equivalent to $1 + x$, because negative of odd is still odd etc.

And $13 + 200x + 999x^2 $ is equivalent to $1 + x^2$ since $200$ becomes $0$ and even times anything is even and so evens act like zero.

[In advanced terms we are working over $GF(2)$]

Now consider $(1 + x)^2 = 1 + 2x + x^2 = 1 + x^2$

Similarly $$(1  + x)^4 = ((1 + x)^2)^2 = (1 + x^2)^2 = 1 + x^4$$

Thus by induction we see that

$$(1 + x)^{2^m} = 1 + x^{2^m}$$

Thus if $n = \sum 2^{e_i}$ (i.e we look at the binary representation of $n$) then

$$(1 + x)^n = \prod (1 + x)^{2^{e_i}} = \prod \left(1 + x^{2^{e_i}}\right)$$

Now

$$\prod \left(1 + x^{2^{e_i}}\right) = \sum x^{m_i}$$

where $m_i$ are exactly the numbers which can be written as the sum of some subset of $2^{e_i}$. Since this gives a binary representation of $m_i$, the representation is unique and the coefficient is $1$.

This proves the above claim.

$\textbf{Additional Remark:}$ This method also works for an arbitrary prime $p$ and we have the following:

$\textbf{Claim:}$ $\binom{n}{k}$ is not divisible by $p$ iff each digit of $k$ in base-$p$ is $\leq$ the corresponding digit in $n$ (in base-$p$).

Note that the characterization we got earlier for $p=2$ is equivalent to this.

Sum of Large and Small divisors of 24n + 1

 Suppose $N = 24n + 1$ is a positive integer, which is not a perfect square. ($n$ is also a positive integer).

A large divisor of $N$ is a divisor of $N$ which is $ > \sqrt{N}$.

A small divisor of $N$ is a divisor of $N$ which is $ < \sqrt{N}$.

Let $L$ be the sum of the large divisors of $N$ and let $S$ be the sum of the small divisors of $N$.

Show that $$ L = S  \mod 24$$ 

For eg, $145 = 29 \times 5$ has the divisors $1, 5, 29, 145$ and $145 + 29 = 6 = 1 + 5 \mod 24$.

Scroll down for a solution.

.

.

.

.

Solution:

Any number $a$ which is relatively prime to $24$ is of the form $a = 6m \pm 1$.

Now $$a^2 - 1 = 36m^2 \pm 12m = 12m (3m \pm 1) = 0 \mod 24$$

This is because $m(3m \pm 1)$ is an even number (either $m$ is even, or $3m \pm 1$ is).

Now since $N$ is not a perfect square, we can pair off the divisors of $N$ as $sl = N$ with $s$ being a small divisor and $l$ being a large divisor.

Note that both $s$ and $l$ are relative prime to $24$, with $sl = 1 \mod 24$.

Now $s^2 - sl =  1 - 1 = 0 \mod 24$, i.e $s(s-l) = 0 \mod 24$. Since $\gcd(s, 24) = 0$, we must have that $s = l \mod 24$.

Thus $\sum s = \sum l \mod 24$.

$\textbf{Additonal Remarks:}$ Similarly we can show that the sum of divisors of a number of the form $24 n - 1$ is divisible by $24$.

Average Sum of Distances

 Given $n$ numbers $0 \le x_i \le 1$, define the function $f:[0,1] \to \mathbb{R}$ as

$$f(x) = \frac{1}{n} \sum_{i=1}^{n} |x - x_i|$$

A) Show that there is some $a \in [0,1]$ such that $$f(a) = \frac{1}{2}$$ 

B) Show that there is some $b \in [0,1]$ such that 

$$f(b) = \frac{1}{2} - \frac{1}{n} \sum_{i=1}^{n} (x_i- x_i^2)$$

Scroll down for a solution.

.

.

.

.

.

Solution:

A) Notice that $|0 - x_i| + |1 - x_i| = 1$ and thus we have that $f(0) + f(1) = 1$.  If $f(0) \leq \frac{1}{2}$ then $f(1) \geq \frac{1}{2}$ and by the intermediate value theorem, there is some $a \in [0,1]$ such that $f(a) = \frac{1}{2}$. Other cases are similar.

B) By the mean value theorem, there is some $b \in [0,1]$ such that

$$f(b) = \int_{0}^{1} f(x) dx$$

Turns out that

$$\int_{0}^{1} f(x) dx = \frac{1}{2} - \frac{1}{n} \sum_{i=1}^{n} (x_i- x_i^2)$$

It is the sum of right angled triangle areas of legs $x_i, x_i$ and $(1-x_i), (1-x_i)$. 

$\textbf{Additional Remark:}$ Result in part B can easily be used to show that if $f(x) \ge \frac{1}{2} \forall x \in [0,1]$, then $n$ must be even, with half the $x_i = 0$ and the rest $ = 1$, and $f$ a constant $= \frac{1}{2}$.

Quadratic root in $(0,1)$

 A nice little problem from the IIT JEE exam.

$a,b,c$ are real numbers such that $$2a + 3b + 6c = 0$$

Show that $ax^2 + bx + c = 0$ has a root in the interval $(0,1)$

Scroll down for a short solution.

.

.

.

.

Solution:

Consider $$ f(x) = 2a x^3 + 3bx^2 + 6cx + d$$

We have that $f(0) = d$ and $f(1) = d$. Thus by Rolle's theorem, there is some $\eta \in (0,1)$ such that $f'(\eta) = 0$.

Now $f'(x) = 6ax^2 + 6bx + 6c = 6(ax^2 + bx + c)$. 

Thus $a\eta^2 + b\eta + c = 0$ and we are done!

A Nice Croatian Math Olympiad problem with $\log_k$ and $k^{th}$ roots

 For a positive integer $n \ge 2$, prove that

$$\left[\log_2 n\right] + \left[\log_3 n\right] + \dots + \left[\log_n n\right] = \left[\sqrt{n}\right] + \left[\sqrt[3]{n}\right] + \dots + \left[\sqrt[n]{n}\right]$$

$[x]$ is the integer part of $x$

Scroll down for a solution.

.

.

.

.

.

.

Solution:

We will show that this equality is basically saying that the sum of sums of rows = sum of sums of columns in a matrix, for a certain matrix.

Consider the $n \times n $ matrix $A$ such that the entry of row $m$ and column $k$ is $1$ if $$\sqrt[m]{n} \ge k$$ and $0$ otherwise.

Since $\sqrt[m]{n} \le n$,  row $m$ has exactly $$\left[\sqrt[m]{n}\right]$$ ones

Thus the sum of sum of rows is

$$ n + \left[\sqrt{n}\right] + \left[\sqrt[3]{n}\right] + \dots + \left[\sqrt[n]{n}\right]$$

Now let us try to count the number of ones in column $k$.

For $k=1$, the numbers of ones is exactly $n$, because $\sqrt[m]{n} \ge 1$ for any $m \ge 1$.

For $k \ge 2$, number of ones will be all the $m$ that satisfy $1 \le m \le n$ and

$$ \sqrt[m]{n} \ge k$$

i.e number of $1 \le m \le n$ such that

$$ \log_k n \ge m$$

Since for $2 \le k$, $\log_k n \le n$, there are exactly $$\left[\log_k n\right]$$ ones in column $k$ 

Therefore the sum of sums of columns is

$$ n + \left[\log_2 n\right] + \left[\log_3 n\right] + \dots + \left[\log_n n\right] $$

Now equating the sum of sums of rows to the sum of sums of columns gives us the result.

An arithmetic limit that gives the geometric mean

 Let $a_1, a_2, \dots a_k$ be positive reals.

Show that

$$ \lim_{n \to \infty} \left(\dfrac{a_1^{\frac{1}{n}} + \dots + a_k^{\frac{1}{n}}}{k}\right)^n = \sqrt[k]{a_1 a_2 \dots a_k}$$

Scroll down for a solution that does not use "calculus".

.

.

.

.

.

A repeated use of (weighted) AM $\ge$ GM does it. 

Using weighted AM-GM we have that

$$\dfrac{x_1 \times \frac{1}{x_1} + \dots + x_k \times \frac{1}{x_k}}{x_1 + \dots + x_k} \ge \sqrt[x_1 + \dots + x_k] { \frac{1}{x_1^{x_1}} \dots \frac{1}{x_k^{x_k}}}$$

And so

$$ x_1^{\frac{x_1}{S}} \dots x_k^{\frac{x_k}{S}} \ge \dfrac{x_1 + \dots + x_k}{k}$$

Where $S = x_1 + \dots + x_k$.

And so we have the following (by adding the classic AM-GM on the right) and taking the $n^{th}$ powers

$$\left(x_1^{\frac{x_1}{S}} \dots x_k^{\frac{x_k}{S}}\right)^n \ge \left(\dfrac{x_1 + \dots + x_k}{k}\right)^n \ge \left(\sqrt[k]{x_1 \dots x_k}\right)^n$$

Now set $x_j = a_j^{\frac{1}{n}}$ (and so $x_j^n = a_j$)

Now as $n \to \infty, \frac{x_j}{S} \to \frac{1}{k}$.

Therefore 

$$\left(x_1^{\frac{x_1}{S}} \dots x_k^{\frac{x_k}{S}}\right)^n = a_1^{\frac{x_1}{S}} \dots a_k^{\frac{x_k}{S}} \to \sqrt[k]{a_1 \dots a_k}$$

We also have

$$\left(\sqrt[k]{x_1 \dots  x_2}\right)^n =  \sqrt[k]{a_1 \dots a_k}$$

Thus $$ \left(\dfrac{a_1^{\frac{1}{n}} + \dots + a_k^{\frac{1}{n}}}{k}\right)^n = \left(\dfrac{x_1 + \dots + x_k}{k}\right)^n \to \sqrt[k]{a_1 \dots a_k}$$

by the sandwich theorem and we are done.

Maximizing a trigonometric expression (IIT JEE prep question with cute solutions)

Found this cute problem in some IIT JEE prep material. The question as posed there, was a single answer multiple choice question, to find the maximum value. Anyway the puzzle here is:

For what $x \in [0, 2\pi]$ does the expression

$$ \cos x (\sin x + \sqrt{\sin^2 x + 1})$$

take the maximum value? What is the maximum value? No calculus allowed.

Scroll down for solutions.

.

.

.

.

.

$\textbf{Method 1}$: One nice method is to use vector algebra. Consider the formula:

$$ u.v = |u | |v| \cos \theta$$

with $u = (\sin x, \cos x),  v= (\cos x, \sqrt{\sin^2 x + 1})$. 

The expression in question (say $f$) is $f = u.v$ with $|u| = 1$ and $|v| = \sqrt{2}$. Thus  $f \leq \sqrt{2}$. $f$ will be $ = \sqrt{2}$ iff $u$ and $v$ are parallel. And so we are looking for solutions of

$$\sin x \sqrt{\sin^2 x + 1} = \cos^2 x$$

Since $\cos x = 0$ cannot be a solution, we can divide by $\cos^2 x$ and rewrite as

$$\tan x \sqrt{\tan^2 x + \sec^2 x} = 1$$

If $t = \tan x$, then this is 

$$ t \sqrt{2t^2 + 1} = 1$$

Which is a quadractic in $t^2$ with the solution $ t  = \frac{1}{\sqrt{2}}$.

Thus $x$ must satisfy $\tan x = \frac{1}{\sqrt{2}}$. We can verify that it is indeed a solution.

$\textbf{Method 2}:$ This is also a nice solution.

Let $$f = \cos x (\sin x + \sqrt{\sin^2 x + 1})$$

Clearly $\cos x = 0$ cannot be it. So assume $\cos x \neq 0$.

Now this looks quite similar to formula for the root of a quadratic.

$$ f = \frac{ - ( -\sin x) + \sqrt{(-\sin x)^2 - 4 \left(\frac{\sec x}{2}\right) \left(\frac{-\cos x}{2}\right)}}{2 \times\frac{\sec x}{2}}$$

Thus $f$ is the root of $ax^2 + bx + c$ with $a = \frac{\sec x}{2}, b = -\sin x, c = \frac{-\cos x}{2}$.

Thus we have that

$$ \frac{\sec x}{2} f^2 - f \sin x - \frac{\cos x}{2} = 0$$

Multiplying by $2\sec x$ gives us

$$ \sec^2 x f^2 - 2f \tan x - 1 = 0$$

i.e

$$f^2 + \tan^2 x f^2 - 2f \tan x = 1$$

$$ f^2 + (f \tan x - 1)^2 = 2$$

Since $(f\tan x -1)^2 \ge 0$, we must have $f^2 \le 2$. For $f^2 = 2$ (and so $f = \sqrt{2}$) we need $f\tan x = 1$, ie $\tan x = \frac{1}{f} = \frac{1}{\sqrt{2}}$. This is easily verified.

A trigonometric problem from IIT JEE 1995

 The IIT JEE 1995 subjective maths paper had some nice problems. Already posted an integral, previously.

Here is a trigonometric one.

Find the smallest positive $\rho$ such that the equation in $x$ $$\cos (\rho \sin x) = \sin (\rho \cos x)$$ has a solution in $[0, 2\pi]$.

Scroll down for a solution.

.

.

.

.

.

Let's first try to find some $\rho$. Notice that for $x = \frac{\pi}{4}$  to be a solution we need $$\cos \left(\frac{\rho}{\sqrt{2}}\right) = \sin\left(\frac{\rho}{\sqrt{2}}\right)$$

We can try $$\frac{\pi}{2} - \frac{\rho}{\sqrt{2}} =  \frac{\rho}{\sqrt{2}}$$

giving us $$\rho = \frac{\pi}{2\sqrt{2}}$$

 Thus the answer we seek must $ \leq \frac{\pi}{2\sqrt{2}}$.

Now if $\cos x = \cos y $ then we must have that $x = 2n\pi \pm y$ and so $\cos (\rho \sin x) = \sin (\rho \cos x)$ gives us

$$\rho \sin x = 2n\pi \pm \left(\frac{\pi}{2} - \rho \cos x\right)$$

i.e

$$\rho (\sin x \pm \cos x) = 2n \pi \pm \frac{\pi}{2}$$

i.e $$ \sqrt{2} \rho \sin (x \pm \frac{\pi}{4}) = 2n\pi \pm \frac{\pi}{2}$$

Since $0 < \rho \le \frac{\pi}{2\sqrt{2}}$  and $|\sin \theta| \leq 1$, we must have that $n = 0$ and

$$\sqrt{2} \rho |\sin (x \pm \frac{\pi}{4})| = \frac{\pi}{2}$$

This implies that $ \rho \geq \frac{\pi}{2\sqrt{2}}$.

Thus the least possible value is $\rho = \frac{\pi}{2\sqrt{2}}$.

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.

A generalization of sum of squares

 Let $A_1, A_2 \dots A_n$ be $n$ points in the 2D plane, with centroid $M$.

Show that for any point $P$ in the plane

$$ \sum_{i = 1}^{n} PA_{i}^2 = n PM^2  + \sum_{i=1}^{n} MA_{i}^2$$

Bonus: Given a magic fairy that tells you the sum of squares of distances of any point $P$ to $A_1, A_2, \dots, A_m$ where you don't know $m$ or the $A_i$, show that you can find $m$ in a finite number of queries to the magic fairy.

Solution

.

.

.

.

.

Surprisingly this has an easy proof using complex numbers!

Let $a_1, a_2, \dots, a_n$ be complex numbers that sum to $0$,

Then we have that for any complex number $z$,

$$\sum_{i=1}^{n} |z-a_i|^2 = \sum_{i=1}^{n} (z-a)\overline{(z-a)} = $$

$$ \sum_{i=1}^{n} (z\overline{z} - z\overline{a_i} -\overline{z}a_i + a_i\overline{a_i}) = $$

$$ n z \overline{z} + \sum_{i=1}^{n} a_i\overline{a_i}  = n |z|^2 + \sum_{i=1}^{n} |a_i|^2$$

This gives us the identity we seek. The centroid $M$ corresponds to $0$, the sum of $a_i$.

The bonus puzzle solution follows along the lines of the previous guessing puzzle, and I will leave it to you.

Cute problem from Moldova Math Olympiad

 $a,b$ are real numbers that satisfy

$$a^3 - 3ab^2 = 29$$

$$b^3 - 3a^2b = 34$$

What is the value of $a^2 + b^2$?

Meta puzzle: Which year did this problem appear?

.

.

.

.

Solution:

The solution becomes simple if you think complex!

$$(a+ib)^3 = (a^3 - 3ab^2) - i(b^3 - 3a^2b)$$

Thus $$(a+ib)^3 = 29 - 34i$$

And so $$(a^2 + b^2)^3 = 29^2 + 34^2 = 1997$$

and

$$a^2 + b^2 = \sqrt[3]{1997}$$

Note that we basically have the identity

$$(a^2 + b^2)^3 = (a^3 - 3ab^2)^2 + (b^3 - 3a^2b)^2$$

Sum of consecutive positive integers

 A classic.

Show that integers of the form $2^m$ are the only positive integers that cannot be written as the sum of two or more consecutive positive integers.

.

.

.

.

Solution:

Suppose we try to write $X$ as the sum of consecutive positive integers.

$$X =  a + (a+1) + \dots + (a+n)$$ 

i.e.

$$2X = (n+2a)(n+1)$$

Note, since we need two or more, we must have that $n > 0$, and $n + 2a > n+1$.

Note that $n+2a$ and $n+1$ are of different parities.

If $X$ was a power of $2$, then the only way we can factor $2X$ into factors of different parities is if one of them is $1$. But we have $n+1 \ge 2$. So, powers of $2$ cannot be written in that form.

For any other $X  = 2^m Y$ ($Y > 1$, odd), we can pick the factors to be $2^{m+1}$ and $Y$ and compute the appropriate $n$ and $a$.

A cute problem form India's UPSC exam

 UPSC is India's civil services exam, and surprisingly, the following cute problem appeared. Admittedly, it was a multiple choice question, and could be guessed easily.

Anyway, here is the question:

$a,b,c$ are positive integers such that 

$$\dfrac{bc + 1}{abc + a + c} = \frac{11}{43}$$

Then what are the possible values of $abc$?

Solution.

We can find all solutions. In fact there is a unique solution.

Take the reciprocal and do some minor algebra to get

$$a + \dfrac{c}{bc + 1} = \dfrac{43}{11} = 3 + \dfrac{10}{11}$$ 

Since $\frac{c}{bc + 1} \lt 1$, we must have that $a=3$ and $\frac{c}{bc+1} = \frac{10}{11}$.

Taking reciprocal again gives

$$b + \dfrac{1}{c} = \dfrac{11}{10} = 1 + \dfrac{1}{10}$$

$c = 1$ is not possible (LHS is an integer, while RHS is not). Thus $\frac{1}{c} \lt 1$ and so

$b = 1$ and $c=10$

Thus $(a,b,c) = (3,1,10)$ is the unique solution and $abc = 30$.

Sqrt and square free

Given a positive integer $n$. Show that

$$ n = \sum_{k} \left[\sqrt{\dfrac{n}{k}}\right]$$

where $k$ runs through the square free numbers, $1 \le k \le n$ and $[x]$ is the integer part of $x$.

Solution:

Simpler solution (earlier complicated solution is still there below)

Every number can be written uniquely in the form $u^2 q$ where $q$ is square free.

Given a square free $q$, there are $[\sqrt{\frac{n}{q}}]$ numbers of the form $u^2q$ which are $\le n$ 

Now just add up for each squarefree $q$.

Complicated solution:

If $\lambda$ is the Lioville function: $\lambda(p^a) = (-1)^a$  for prime powers and $\lambda(ab) = \lambda(a)\lambda(b)$ for co-prime $a,b$

then using dirichlet convolution we have the identity $\lambda * 1 = s$, where $s$ is the indicator function for perfect squares. 

We can also show that the dirichlet inverse of $\lambda$ is $\mu^2$, where $\mu$ is the mobius function.

Thus we have $1 = \lambda^{-1} * s$

Which gives (using summation identities involving dirichlet convolution)

$$ n  = \sum_{1 \le k \le n} \mu^2(k) S(n/k)$$

where $S(n/k)$ counts the number of perfects squares $ \le \frac{n}{k}$, which is in fact $\left[\sqrt{\frac{n}{k}}\right]$.

$\mu(k)$ is non-zero only for the square free numbers, and that proves the identity,

3 consecutive summing to 13

 You permute each of the digits $0, 1,2, \dots, 9$ and write them in a single row.

A) Show that no matter what the permutation, some 3 adjacent elements of the row sum to at least $13$.

B) Can you find a permutation where no 3 adjacent elements sum to more than $13$?

Scroll down for solution

.

.

A) Say the permutation is $x_0, x_1, \dots, x_9$.

Now one of $x_0$ or $x_9$ is $< 9$. We can assume $x_0 < 9$.

Let $S_i = x_i + x_{i+1} + x_{i+2}$.

Since $x_0 < 9$ we must have that $S_1 + S_4 + S_7 > 36$ and thus $\text{max} \{S_1, S_4, S_7\} > 12$.

B)  9 3 1 7 4 2 6 0 5 8

Peter Winkler's factorial problem

 A cute problem from Peter Winkler's collection of math puzzles.

$$ S = \{n! | 1 \leq n \le 100, n \in N\}$$

Can we remove a single element from $S$ such that the product of the elements of the resulting set is a perfect square?

Scroll down for a solution.

Product of elements of $S$ is

$$ P = 1!  2! \dots 99!  100! $$

Pair up terms $(2n-1)! (2n)! = ((2n-1)!)^2 2n$

Thus

$$P = (1!  3!  5! \dots 99!)^2 (2 . 4 . 6 \dots 100) $$

$$ =  (1!  3!  5! \dots 99!)^2 . 2^{50} . 50!$$

Thus removing $50!$ from $S$ will give us the desired result.

Exactly 80% success

A basketball player is practising free throws. Their current success rate (ratio of successful throws to total) is exactly 70% (or 0.7 in terms of ratio). After a few more throws that success rate is 90%. 

Show that at some point the success rate was exactly 80%.

Scroll down for a solution

.

Look at (misses, hits) on the integer lattice and x-y coordinate plane. If a miss occurs, we increment x coordinate, else we increment y coordinate.

Initially we are on the line $3y = 7x$ (70% hit rate) and reach the line $y = 9x$ (90% hit rate), crossing the line $y = 4x$ (80% hit rate) at some point, with some hit (i.e by incrementing the y-coordinate).,

The only way to cross the line $y = 4x$ vertically is to actually land on it first (every x = N line intersects y = 4x at (N, 4N) which is part of the integer lattice. Thus we achieve exactly 80%,

Product of three consecutive positive integers

 Can the product of three positive consecutive integers be a perfect square?

Scroll down for a solution

.

Assume the three integers are $n-1, n, n+1$ and that $(n-1)n(n+1)  = n(n^2-1)$ is a perfect square.

Since $n$ is relatively prime to both $n-1$ and $n+1$ (and hence their product $n^2-1$), we must have that $n^2-1$ is a perfect square too.