AMM problem 12449

This is AMM problem 12449 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

Let $n$ be a positive integer with $n\ge 2$. The squares of an $(n^2+n-1)$-by-$(n^2+n-1)$ grid are colored with up to $n$ colors. Prove that there exist two rows and two columns whose four squares of intersection have the same color.

Solution -

Define a monochromatic $i$-pair as an unordered pair of row indices of squares in the same column with the same color $i$.

Note that if the same $i$-pair appears in two distinct columns, we have found a monochromatic rectangle. If not, each column must contribute distinct $i$-pairs, making the maximum number of possible $i$-pairs $(\genfrac{}{}{0ex}{}{n^2+n-1}{2})$, hence the maximum number of monochromatic pairs $n\cdot (\genfrac{}{}{0ex}{}{n^2+n-1}{2})$.

But if the $k$-th column contains $k_i$ squares of color $i$, then it contributes

$$\sum _{i=1}^n(\genfrac{}{}{0ex}{}{k_i}{2})$$

monochromatic pairs, which is minimized when one $k_i$ is $n$ and the remaining $n-1$ many $k_i$ are $n+1$.

Thus, the $k$-th column contributes at least

$$(\genfrac{}{}{0ex}{}{n}{2})+(n-1)(\genfrac{}{}{0ex}{}{n+1}{2})=\frac{n\cdot (n^2+n-2)}{2}$$

monochromatic pairs, giving a total of at least

$$\frac{(n^2+n-1)\cdot n\cdot (n^2+n-2)}{2}=n\cdot (\genfrac{}{}{0ex}{}{n^2+n-1}{2})$$

monochromatic pairs.

Since we have equality, each color $i$ must contribute the same number (i.e. $(\genfrac{}{}{0ex}{}{n^2+n-1}{2})$) of $i$-pairs, while simultaneously all $k_i\in \{n,n+1\}$. The latter means that each color $i$ must contribute a multiple of $n$ many $i$-pairs, whereas

$$n\nmid (\genfrac{}{}{0ex}{}{n^2+n-1}{2})$$

which is a contradiction. $◻$

AMM problem 12448

This is AMM problem 12448 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

Given real numbers $a_1,\dots ,a_n$. Prove

$$S_1\sqrt{n{S}_2}\le S_1^2+\frac{1}{2}\lfloor \frac{n^2}{4}\rfloor {(\underset{i}{max}{a}_i-\underset{i}{min}{a}_i)}^2$$

where $S_1=\sum _{i=1}^n{a}_i$ and $S_2=\sum _{i=1}^n{a}_i^2$.

Solution -

Without loss of generality, let $a_1\le \cdots \le a_n$ and $S_1>0$.

Setting $\mu =S_1/n$, we need to prove 

$$\mu \sqrt{{\sigma }^2+{\mu }^2}\le {\mu }^2+\frac{1}{2}\lfloor \frac{n^2}{4}\rfloor \frac{(a_n-a_1{)}^2}{n^2}$$

where ${\sigma }^2=\frac{1}{n}\sum _{i=1}^n(a_i-\mu {)}^2=\frac{S_2}{n}-{\mu }^2$.

Squaring both sides, this is equivalent to

$$\begin{array}{}\text{(}\star \text{)}& {\sigma }^2\le \lfloor \frac{n^2}{4}\rfloor \frac{(a_n-a_1{)}^2}{n^2}+\frac{1}{4{\mu }^2}{\left(\lfloor \frac{n^2}{4}\rfloor \frac{(a_n-a_1{)}^2}{n^2}\right)}^2\end{array}$$

since $\mu >0$.

Let ${\mu }_{\mathbf{x}}=\frac{1}{n}\sum _i{x}_i$ and ${\sigma }_{\mathbf{x}}^2=\frac{1}{n}\sum _i(x_i-{\mu }_{\mathbf{x}}{)}^2$ for real numbers $x_1,\dots ,x_n$.

Since ${\sigma }_{\mathbf{x}}^2$ is a smooth convex function of $\mathbf{x}$, it attains its maximum on $[a,b{]}^n$ at an extreme point, i.e. when all $x_i\in \{a,b\}$.

If exactly $k$ many $x_i$ are equal to $a$ and $n-k$ many are equal to $b$, we have

$${\sigma }_{\mathbf{x}}^2=\frac{k(n-k)}{n^2}(b-a{)}^2.$$

Now, $(n-2k{)}^2\ge 0$ gives $k(n-k)\le n^2/4$, forcing $k(n-k)\le \lfloor n^2/4\rfloor$.

Thus, 

$$\underset{\mathbf{x}\in [a,b{]}^n}{max}{\sigma }_{\mathbf{x}}^2\le \lfloor \frac{n^2}{4}\rfloor \frac{(b-a{)}^2}{n^2}$$

and ${\sigma }^2\le \lfloor n^2/4\rfloor (a_n-a_1{)}^2/n^2$, from which ($\star$) follows directly. $◻$

Another Needlessly Sophisticated Proof of a Simple Result

This post belongs solely to a genre that should be called "joke proofs". The only thing a joke proof provides (except an awfully sophisticated argument for a very simple result) is intellectual stimulation. Some very well known contributions to this field are a proof of irrationality of $2^{1/n}$ using Fermat's Last Theorem or a proof of infinitude of primes using irrationality of $\zeta (3)$ (although infinitude of primes have received some more suspicious entries as well).

The following theorem (if you can call it a theorem) follows directly from looking at the integers $\{(k+1)!+\ell {\}}_{\ell =2}^{k+1}$. But our proof instead uses two other well known results, namely the fact that the sum of reciprocals of primes diverges (proof) and something slightly stronger than the fact that the sum of reciprocals of twin primes converges (proof). It is well known that an exact same proof technique runs through to show that if ${\mathcal{S}}_k=\{p\in \mathcal{P}:p+k\in \mathcal{P}\}$ where $\mathcal{P}$ is the set of primes, then $\sum _{s\in {\mathcal{S}}_k}\frac{1}{s}$ converges. This is what we will use in the proof.

As far as my knowledge goes (which is not too far), this proof is completely original, although that's not something to be very proud of!

Theorem : For any given $k$, there exists $k$ consecutive composite numbers.

Proof : If possible, let

$$\underset{p_1,p_2\text{ are consecutive primes}}{sup}|p_1-p_2|=B$$

for some integer $B$.

Then

$$\sum _{i=1}^B\sum _{p,p+i\in \mathcal{P}}\frac{1}{p}\ge \sum _{p\in \mathcal{P}}\frac{1}{p}$$

where $\mathcal{P}$ is the set of primes.

The LHS converges by Brun sieve and the RHS diverges, hence giving a contradiction! $◻$

AMM problem 12435

This is AMM problem 12435 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

For a positive integer $n$, let $d(n)$ be the number of positive divisors of $n$, let $\varphi (n)$ be Euler's totient function, and let $q(n)=d(\varphi (n))/d(n)$. Find $\underset{n}{inf}q(n)$ and $\underset{n}{sup}q(n)$.

Solution -

We claim that $\underset{n}{inf}q(n)=0$ and $\underset{n}{sup}q(n)=\mathrm{\infty }$.

To show that $\underset{n}{sup}q(n)=\mathrm{\infty }$, note that $q(p)=d(p-1)/2$ for primes $p$, which can be made arbitrarily large. Indeed, for any $\ell \in \mathbb{N}$, the arithmetic progression $\{\ell !k+1{\}}_{k\in \mathbb{N}}$ must contain a prime $p^{\prime }$ (due to Dirichlet) whence $p^{\prime }-1=\ell !k^{\prime }$ has at least $M$ divisors so that $d(p^{\prime }-1)\ge \ell$.

Next, we show that $\underset{n}{inf}q(n)=0$. To do so, we choose arbitrary $m\in \mathbb{N}$ and find $N$ such that $q(N)\le 1/2^{m-1}$. Pick a sequence ${\mathcal{Q}}_m$ of $m$ primes $q_1\le \cdots \le q_m$ such that $q_m<2q_1$; we will show later that this is always possible via the Prime Number Theorem. Let $\mathcal{P}=\{p_1,\dots ,p_n\}$  be all the primes less than $q_1$. Note that each $q_i-1$ and each $p_j-1$ can be factored solely in terms of the primes from $\mathcal{P}$.

For $k_1,\dots ,k_n\in \mathbb{N}$, consider

$$N=N(k_1,\dots ,k_n)=p_1^{k_1}\cdots p_n^{k_n}\times q_1\cdots q_m,$$

With this, we have 

$$d(N)=(k_1+1)\cdots (k_n+1)\times 2^m$$

and

$$\begin{array}{rl}\varphi (N)& =p_1^{k_1-1}\cdots p_n^{k_n-1}\times (p_1-1)\cdots (p_n-1)\times (q_1-1)\cdots (q_m-1)\\ & =p_1^{k_1+{\alpha }_1-1}\cdots p_n^{k_n+{\alpha }_n-1}\end{array}$$

where the integers ${\alpha }_j\ge 0$ depend only on ${\mathcal{Q}}_m$. Thus,

$$d(\varphi (N))=(k_1+{\alpha }_1)\cdots (k_n+{\alpha }_n)$$

and

$$q(N(k_1,\dots ,k_n))=\left(\frac{k_1+{\alpha }_1}{k_1+1}\right)\cdots \left(\frac{k_n+{\alpha }_n}{k_n+1}\right)\times \frac{1}{2^m}.$$

Taking $min\{k_1,\dots ,k_n\}\to \mathrm{\infty }$, we can make $q(N(k_1,\dots ,k_n))$ arbitrarily close to $1/2^m$, in particular less than $1/2^{m-1}$.

To prove the existence of ${\mathcal{Q}}_m$ for each $m\in \mathbb{N}$, it is enough to show that there is $n\in \mathbb{N}$ such that $[n,2n]$ contains at least $m$ primes. By the Prime Number Theorem, the number of primes in $[n,2n]$ is of the order

$$\frac{2n}{\log (2n)}-\frac{n}{\log (n)}\sim \frac{n}{\log (n)}$$

which grows arbitrarily large as $n\to \mathrm{\infty }$.

Note : Here's an easier proof of $\underset{n}{inf}q(n)=0$ assuming that there are infinitely many Fermat primes. Consider the sequence

$$N=2^k\cdot F_1\dots F_n$$

where $F_1,\dots ,F_n$ are the first $n$ Fermat primes. This gives

$$q(N)=\frac{k+{\alpha }_1+\cdots +{\alpha }_n}{k+1}\times \frac{1}{2^n}$$

where $F_i=2^{{\alpha }_i}+1$. Taking $k$ and $n$ to infinity, we complete the proof.

Thanks to this argument, if $\underset{n}{inf}q(n)\ne 0$, then that implies that there are only finitely many Fermat primes, which resolves a long standing conjecture about Fermat primes. Since that is highly unlikely, the $inf$ has to be $0$ - this is a classic case of proof by existence of proof!

AMM problem 12377

This is my first post (or second, depending on how you look at the world). For this, I decide to post the first AMM problem I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

We define a one-drop number as in problem 12377 from Problems and Solutions, The American Mathematical Monthly, Volume 130, 2023, Issue 3.

An integer is a one-drop number if its decimal digits $d_1,\dots ,d_n$ satisfy

$$1\le d_1\le d_2\cdots \le d_i>d_{i+1}\le \cdots \le d_n$$

for some $i$, with $1\le i<n$.

For example, the numbers $13802$ and $49557$ are one-drop numbers, while the numbers $12345$ and $352712$ are not.

We answer the following question: for $n\ge 2$, how many $n$-digit one-drop numbers are there?

Solution -

There are

$$(\genfrac{}{}{0ex}{}{n+18}{18})-(\genfrac{}{}{0ex}{}{n+9}{9})-n\cdot (\genfrac{}{}{0ex}{}{n+8}{8})$$

one-drop numbers of length $n\ge 2$.

The digits of every $n$-digit one-drop number $d_1,\dots ,d_n$ can be uniquely split into two zero-drop blocks $A$ and $B$, with digits $1\le d_1\le \cdots \le d_i$ and $0\le d_{i+1}\le \cdots \le d_n$. Here, is a zero-drop block consists of a sequence of non-decreasing decimal digits; we allow the leading digit to be $0$.

Consider all $19$-tuples $(a_1,\dots ,a_9,b_0,b_1,\dots ,b_9)$ of non-negative integers such that

$$a_1+\cdots +a_9+b_0+b_1+\cdots +b_9=n.$$

Each tuple represents an $n$-digit number obtained by concatenating two zero-drop blocks $A$ and $B$, where $a_d$ and $b_d$ denote the number of occurrences of the digit $d$ in the respective blocks. Clearly, there are $(\genfrac{}{}{0ex}{}{n+18}{18})$ such tuples. Note that each tuple of this kind represents either a zero-drop or a one-drop number, and each $n$-digit one-drop number is uniquely represented by such a tuple.

Discard all tuples where the block $A$ is empty, with all $a_d=0$; the corresponding number is zero-drop. There are as many such tuples as there are non-negative integer solutions of 

$$b_0+b_1+\cdots +b_9=n,$$

that is, $(\genfrac{}{}{0ex}{}{n+9}{9})$. This leaves $(\genfrac{}{}{0ex}{}{n+18}{18})-(\genfrac{}{}{0ex}{}{n+9}{9})$ tuples; call this set of tuples $S$. Note that for any element in $S$, the block $A$ is non-empty. Thus, it represents a proper $n$-digit number since the leftmost digit is non-zero.

Suppose that a tuple $(a_1,\dots ,a_9,b_0,b_1,\dots ,b_9)\in S$ represents a zero-drop number. Since some $a_d>0$, the digit $0$ cannot appear in block $B$, hence the number consists only of digits $1$ through $9$. There are $(\genfrac{}{}{0ex}{}{n+8}{8})$ such $n$-digit zero drop numbers, via counting the non-negative integer solutions of

$$c_1+\cdots +c_9=n.$$

Each of these numbers has been represented by precisely $n$ tuples from $S$, because the first $i$ digits of such a number can be placed in block $A$ with the remaining digits in block $B$ for all $1\le i\le n$.

For example, the $5$-digit zero-drop number $11234$ can be broken into blocks $A,B$ as $1,1234$ or $11,234$ or $112,34$ or $1123,4$ or $11234,\mathrm{\varnothing }$, each of which correspond to distinct tuples from $S$.

Thus, precisely $n\cdot (\genfrac{}{}{0ex}{}{n+8}{8})$ tuples from $S$ represent zero-drop numbers. The remaining $(\genfrac{}{}{0ex}{}{n+18}{18})-(\genfrac{}{}{0ex}{}{n+9}{9})-n\cdot (\genfrac{}{}{0ex}{}{n+8}{8})$ tuples uniquely represent all $n$-digit one-drop numbers. $◻$

Hello World

Hey there!

I am Sayan Dutta, a student of mathematics interested in Number Theory and Combinatorics. I completed my BS-MS from IISER Kolkata and I will be joining a PhD program in 2025 in University of Montreal under Prof. Dimitris Koukoulopoulos. Before that, I completed my Masters' thesis under the supervision of Prof. Ramachandran Balasubramanian and Prof. Soumya Bhattacharya. My thesis was on Sidon sets and can be found in my website.

A far less boring description of me was given by my dear friend Sohom Gupta

Sayan Dutta is an undergraduate student of mathematics, interested in discrete mathematics and vibrant patterns hidden in the simplest of structures. His appreciation of beauty stems from his cinephile present, while his chess moves are just nuances of perfection. He aspires to paint the world in the language of mathematics and the blossoms of the silver screen.

Inspired by What's new, Joni's Math Notes and others, I decided to keep a blog of my own. As of now, I don't have any particular plans and will post anything I have in mind (only related to mathematics). We will see where this goes!