Nirajan is trapped in a magical dungeon. He has infinitely many magical cards with arbitrary MPs(Mana Points) which is always an integer $\mathbb{Z}$. To escape, he must give the dungeon keeper some magical cards whose MPs add up to an integer with at least $2024$ divisors. Can Nirajan always escape? ( Proposed by Vlad Spǎtaru, Romania)
Problem
Source:
Tags: combinatorics, number theory
wardtnt1234
17.03.2024 17:15
The answer is yes. Pick $2n - 1$ random card. Note that by a theorem (I can't recall the name), we can always choose $n$ cards with sum divisible by $n$. Pick $n = 2^{2024}$ and we are done
khan.academy
17.03.2024 17:21
that would be pigeon hole principle
dhruvtalreja4
17.03.2024 17:23
wow, thats crazy
vsamc
17.03.2024 18:00
Yes. Consider the set of residues modulo $2^{2023}$. Then, by infinite pigeonhole, there exists a residue in the sequence of cards infinitely many times. Therefore, we can take $2^{2023}$ cards which have this same residue and their sum is divisible by $2^{2023}$, so it has at least $2024$ divisors. $\blacksquare$
DroneChaudhary
17.03.2024 19:35
My First AOPS post
Let '$k$' be the smallest positive integer with $2024$ divisors. Consider the infinite numbers modulo $k$; by the infinite pigeonhole principle, there exists a residue $t$ that occurs infinitely many times. In other words, there exists a sub-sequence $a_1, a_2, \dots , a_{k-1}, a_k, \dots$ such that $a_i \equiv t \mod{k}$ for all $i \in \mathbb{N}$
now Nirajan can choose his sum to be the first $k$ elements of this sub-sequence.
$$S = a_1 + \dots + a_k \equiv t + \dots + t = k \times t \equiv 0 \pmod{k}$$$$\iff S = k \times z$$for some integer $z$ and so...
$$d(S) = d(kz) \geq d(k) = 2024$$
Martin2001
17.03.2024 19:47
could the problem still be done if it was "exactly" instead of "at least"?
eduD_looC
17.03.2024 19:49
Martin2001 wrote: could the problem still be done if it was "exactly" instead of "at least"? Answer would be no. If every magical card of his is in the form $2^{2024}d$, then the sum will always have at least $2025$ divisors.
khan.academy
18.03.2024 05:48
Another solution I found in the student's paper: Let, $a_i$ denote the arbitrary MPs, then take a sum $S_i$ such that: $S_k = \sum_{i=1}^k a_i$ Now, suppose there is an integer $m$ with $2024$ divisors, then, we can see that if we choose $m+1$ integers, then by pigeon-hole principle, we are guaranteed to have two $S_a$ and $S_b$ such that $$S_a \equiv S_b \pmod{m}$$By the nature of $S_k$, we are guaranteed to have a sum of cards that has $2024$ divisors or more. Proved. $\blacksquare$