I recently came across the following number theoretic puzzle. Suppose I've infinitely many cards, each with a natural number written on it. Given any $n\in \mathbb N$, the number of cards which have a divisor of $n$ written is exactly equal to $n$. I need to show that every natural number appears on at least one card. Any ideas on how to proceed?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ I deleted my comment (because I didn't initially understand the question), but it still stands ($n = 1$ is always going to be a problem)...it must be removed, yes? $\endgroup$– JaredCommented Oct 4, 2014 at 6:11
-
2$\begingroup$ Why is $n=1$ a problem? For $n=1$, since 1 is the only divisor of 1, we can conclude that 1 appears on (at least) 1 card. What's the problem? $\endgroup$– adrijaCommented Oct 4, 2014 at 6:13
-
$\begingroup$ I'm trying to understand your constraint. Given any $n$, say $n = 1$, then the number of cards which have a divisor of $n$, say $n = 1$ (which will be every natural number), will be equal to $n$ (which would be $n = 1$ in this case). $\endgroup$– JaredCommented Oct 4, 2014 at 6:18
-
$\begingroup$ Here's an example, let's say our set is $\{1,2\}$. Let $n = 1$. The number of cards which have divisors of $1$ are both $1$ and $2$ which means the number of cards which have divisor equal to $n = 1$ is $2 \neq 1$. What am I missing here (I'm sure it's something). $\endgroup$– JaredCommented Oct 4, 2014 at 6:25
-
1$\begingroup$ Suppose $n=1$. 1 is the only divisor, so 1 appears on exactly 1 card. Please ignore the bracketed at least in my previous comment. 1 appears on exactly 1 card. For any other $n$, say $n=10$, note that 10 has the divisors 1,2,5 and 10. So, 1,2,5 and 10 together appear on 10 cards. For a prime $n$, say $n=5$, there are 2 divisors and 1 appears on exactly 1 card. So 5 (and actually, any prime $p$) appears on 4 ($p-1)$ cards. Now what? $\endgroup$– adrijaCommented Oct 4, 2014 at 6:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
7
You're looking for a function $f:\mathbb{N}\to\mathbb{N}$ such that $\sum_{d\mid n} f(d) = n$ for all $n$.
The key is that this determines $f(n)$ if you know $f(1), f(2), \ldots ,f(n-1)$ already. So if you can find any $g$ that does the job, then $f=g$ follows from induction. How to find such a function?
Hint #1: In a cyclic group with $n$ elements, how many elements of order $d$ are there?
Hint #2: How many $n$-th roots of unity are there? How many of those are primitive $d$-th roots of unity?
answered Oct 4, 2014 at 6:25
-
1$\begingroup$ Stated as in the first line, one can directly appeal to the Mobius Inversion formula to find $f(d)$. (Though that feels a bit like using a crane to crush a fly.) $\endgroup$ Commented Oct 4, 2014 at 6:26
-
2$\begingroup$ Doesn't the totient function fit the bill? $\endgroup$– adrijaCommented Oct 4, 2014 at 6:27
-
$\begingroup$ Yes, definitely :D. $\endgroup$– user71641Commented Oct 4, 2014 at 6:28
-
$\begingroup$ Got it, thanks. This $was$ easy, it seems. Just needed to prove the uniqueness part. $\endgroup$– adrijaCommented Oct 4, 2014 at 6:29
-
$\begingroup$ @Semiclassical You can, but how to show that the result is always positive? $\endgroup$ Commented Oct 4, 2014 at 6:30
$\begingroup$
$\endgroup$
1
I came up with the following formulae, not sure if they are entirely correct: If i and p (here p is a prime and i is any integer) are coprime then #(ip) = (p-1).#i Else, #(ip) = p.#i
Where, #k represents the number of cards with number k written on them. For example, #(1) = 1, #(2) = 1 (in general for a prime q, #q = q-1)
Now assume that k is the smallest of the numbers that are absent on the cards. Basically we assume that for all i < k, #i>0. Now, there are three options for k: 1. k is a prime, in which case, #k = k-1 > 0; or 2. k is of the form, k = ip (p is a prime) where: 2a. i and p are coprime. Then, #k = (p-1).#i > 0; or 2b. p divides i. Then, #k = p.#i > 0; or 3. k= 1, where obviously #k = 1 > 0
Since in each case we have a contradiction, our assumption was invalid which means all integers are present at least once.
-
$\begingroup$ Welcome to MSE. Please use MathJax to format your answer. $\endgroup$– user507623Commented Feb 18, 2018 at 22:03