not sure if discussion is allowed yet, but if it is,

jj_ca888 wrote: not sure if discussion is allowed yet, but if it is,

I guess you can cuz it is after 24 hours everyone finished around 3pm est yesterday

CANBANKAN wrote:

This is exactly what I did

I spent way too long trying to find a pairing argument.

CT17 wrote: I spent way too long trying to find a pairing argument.

A pairings argument should exist and work, where we match each term in the left hand side with each term in the right hand side such that <= is preserved. Although this is messy.

Let $d(k)$ denote the number of positive integer divisors of $k$. For example, $d(6) = 4$ since $6$ has $4$ positive divisors, namely, $1, 2, 3$, and $6$. Prove that for all positive integers $n$, $$d(1) + d(3) + d(5) +...+ d(2n - 1)\le d(2) + d(4) + d(6) + ... + d(2n).$$

I spent quite some time finding a pairing argument, but I ended looking at the divisors and their multiples. Attached is the crucial idea in my soultion

Here you can find the official solutions https://cms.math.ca/competitions/cmo/

See that $$\sum_{1\leq k\leq 2n}(-1)^kd(k)=\sum_{1\leq 2j\leq n}\left\lfloor\frac{2n}{2j}\right\rfloor-\sum_{1\leq 2l+1\leq 2n}\left(\left\lfloor\frac{2n}{2l+1}\right\rfloor\text{ }(mod.2)\right),$$and since $\sum_{1\leq 2l+1\leq 2n}\left(\left\lfloor\frac{2n}{2l+1}\right\rfloor\text{ }(mod.2)\right)\leq n-1$ and $\sum_{1\leq 2j\leq n}\left\lfloor\frac{2n}{2j}\right\rfloor\geq n$, we get the desired result. $\blacksquare$

Here is my solution: https://calimath.org/pdf/CMO2022-2.pdf And I uploaded the solution with motivation to: https://youtu.be/W5S-mL5JT7I

Notice that the inequality holds for $n=1,2,3$, for now on assume $n>3$. We will prove the following equivalent statement \[ \sum_{k=1}^n d(2k) > \sum_{k=2}^n d(2k-1) \]For any positive integer $\ell$ let $f_\ell(x)$ denote the number of elements in the set $\{2,4,6 \ldots, 2x \}$ with exactly $\ell$ divisors and $g_\ell(x)$ denote the number of elements in $\{ 3,5,7, \ldots, 2x-1 \}$ with exactly $\ell$ divisors. Claim: For all $\ell > 2$ we have $f_\ell(x) \geq g_\ell(x)$ Let $a_m$ is the $m$'th smallest odd number with $\ell$ divisors. We can change one of the primes dividing $a_m$ into a $2$ creating a new even number $b_\ell$ with $\ell$ divisors. So, we have a new sequence of evens $b_1<b_2< \cdots$ all with $\ell$ divisors and obeys $b_i < a_i$ for all $i$. Thus, the $m$'th smallest even number with $\ell$ divisors is strictly less that the $m$'th smallest odd with $\ell$ divisors. This implies the claim. $\square$ Notice that \[ \sum_{k=1}^n d(2k) > \sum_{k=2}^n d(2k-1) \Longleftrightarrow \sum_{k=2}^n kf_k(n) > \sum_{k=1}^n kg_k(n)\]We see $g_2(n) > f_2(n)$ since this just counts primes. (Handwaving) The LHS is putting more weight on bigger numbers, so it is bigger. The RHS is only putting more weight on $2$ than the LHS, which is the smallest number.

In fact, a much stronger inequality holds: $$d(1) + d(3) + d(5) +...+ d(2n - 1)\le d(1) + d(2) + d(3) + ... + d(n)$$It is easy to see that, for $1\le k\le n$, the number of multiples of $2k-1$ in $1,3,5,...,2n-1$ is $\lfloor\frac{n+k-1}{2k-1}\rfloor$, and the number of multiples of $k$ in $1,2,...,n$ is $\lfloor\frac{n}{k}\rfloor$. By double counting, we have $d(1) + d(3) + d(5) +...+ d(2n - 1)=\sum_{k=1}^n \lfloor\frac{n+k-1}{2k-1}\rfloor$ and $d(1) + d(2) + d(3) + ... + d(n)=\sum_{k=1}^n \lfloor\frac{n}{k}\rfloor$. Because $\frac{n}{k}-\frac{n+k-1}{2k-1}=\frac{(n-k)(k-1)}{k(2k-1)}\ge 0$, we have $\lfloor\frac{n+k-1}{2k-1}\rfloor\le\lfloor\frac{n}{k}\rfloor$ for $1\le k\le n$. Therefore $\sum_{k=1}^n \lfloor\frac{n+k-1}{2k-1}\rfloor\le\sum_{k=1}^n \lfloor\frac{n}{k}\rfloor$, so $d(1) + d(3) + d(5) +...+ d(2n - 1)\le d(1) + d(2) + d(3) + ... + d(n)$. In my opinion, this form is more interesting than the original statement, because not only is it much stronger, but there are several equality cases: equality holds for $n=1,2,3,5$.

Here is a solution with a pairing argument. We will prove a much stronger inequality $$d(1) + d(3) + d(5) + \ldots + d(2n - 1)\le d(1) + d(2) + d(3) + \ldots + d(n).$$ Let $A\subset\mathbb N^2$ be the subset of pairs of positive integers $(x,y)$ such that $x,y$ are odd and $xy\le 2n-1$. Let $B\subset\mathbb N^2$ be the subset of pairs of positive integers $(x,y)$ such that $xy\le n$. We have $LHS=|A|$ and $RHS=|B|$, so it is equivalent to prove that $|A|\le |B|$. Define a function $f\colon A\to\mathbb N^2$ by $f(x,y)=\left(\frac{x+1}{2},\frac{y+1}{2}\right)$. The function $f$ is well-define since $x,y$ are both odd for every $(x,y)\in A$. Moreover, the function $f$ is injective. Hence, it suffices to prove that $\text{Im}(f)\subset B$. Let us fix some $(p,q)\in A$. Since $p,q$ are both positive integers, it follows that: \begin{align*} & (p-1)(q-1)\ge 0\\ &\implies (p+1)(q+1)\le 2(pq+1)\\ &\implies\frac{p+1}{2}\cdot\frac{q+1}{2}\le\frac{pq+1}{2}\le\frac{2n-1+1}{2}=n\\ &\implies f(p,q)\in B. \end{align*} This proves that $\text{Im}(f)\subset B$.