1
$\begingroup$

Problem: Define a mapping $\gamma\colon\mathbb{N}\to\mathbb{N}$ such that for each $n\in\mathbb{N}$ the equation $\gamma(x)=n$ has infinitely many solutions.

Book solution: Let $p_n$ denote the $n$th prime ($p_1=2, p_2=3, \ldots$). Define $\gamma$ by $\gamma(p_n^k)=n$ for $k=1,2,3,\ldots$; $\gamma(m)$ can then be anything for $m$ not a prime power.

My solution: Define $\gamma$ by $\gamma(n\cdot\cos(\pi/2\cdot k))=n$ for $k=1,2,3,\ldots$. Doesn't this work? It seems like there are so many trivial ways to answer this problem correctly or am I missing something?

$\color{red}{\text{Edit: Concerning the book's solution:}}$ Suppose $\gamma(x)=5$. Then solutions are $$p_5^k=11^k=\underbrace{11,121,\ldots}_{\text{infinitely many}},$$ where there are evidently infinitely many solutions. Is my understanding correct?

$\endgroup$
  • $\begingroup$ There are, indeed, many simple answers. But yours isn't clear. What's wanted is a single function $\gamma(x)$. I don't know whether you are defining a single function, or infinitely many functions, one for each $k$. $\endgroup$ – Gerry Myerson Mar 8 '15 at 11:31
  • $\begingroup$ @GerryMyerson Is the book's clearer? $\endgroup$ – riddler Mar 8 '15 at 11:34
  • $\begingroup$ To me, yes, it is. $\endgroup$ – Gerry Myerson Mar 8 '15 at 11:39
  • 1
    $\begingroup$ In response to your edit: yes, your understanding certainly appears to be correct. $\endgroup$ – G. H. Faust Mar 9 '15 at 9:01
4
$\begingroup$

The books solution is very nice. Yours doesn't work, because $\cos(\frac{\pi}{2} \cdot k)$ will only produce a few different values as $k$ varies. So even though you've constructed a different equation that has infinite solutions (all the $k$s), the solutions to the new equation don't all produce distinct solutions to the original equation.

Here's how I would do it, in the style of the book's solution to your other question.

$\gamma(0) = 0,$

$\gamma(1) = 0, \gamma(2) = 1,$

$\gamma(3) = 0, \gamma(4) = 1, \gamma(5) = 2,$

$\gamma(6) = 0, \gamma(7) = 1, \gamma(8) = 2, \gamma(9) = 3,$

And so on.

$\endgroup$
  • $\begingroup$ Or what would be the formula for $\gamma(k)=n$ in this case? Or is that a more difficult question? $\endgroup$ – riddler Mar 8 '15 at 12:04
  • 1
    $\begingroup$ Not strictly. Before, the bound was just giving you a way to compute the value of the function. But it is related, in that a number of the form $\frac{n(n-1)}{2}$ will always be zero. It's still not a nice formula, but I think another way to express $\gamma(k)$ would be: $k - \frac{a(a-1)}{2}$, where $a$ is picked as large as possible without making the function negative. $\endgroup$ – G. H. Faust Mar 8 '15 at 12:08
  • 1
    $\begingroup$ Thanks for your help. I'll digest this more thoroughly once I get some much needed sleep. I understand the book's solution now. Good to have other viewpoints though. Thanks! $\endgroup$ – riddler Mar 8 '15 at 12:16
4
$\begingroup$

$\newcommand{\N}[0]{\mathbb{N}}$The general recipe is to write $\N$ as the union of infinitely many infinite disjoint subsets $A_{n}$, for $n \in \N$, and then define $\gamma(x) = n$ for $x \in A_{n}$, that is, $A_{n} = \gamma^{-1}(\{ n \})$.

My favourite example, which comes from Hilbert's hotel, is to take, for $n \ge 1$ $$ A_{n} = \{ x \in \N : x \equiv 2^{n-1} \pmod{2^{n}} \}, $$ So $A_{1}$ are the odd numbers, $A_{2}$ are the numbers congruent to $2$ modulo $4$, etc

$\endgroup$
0
$\begingroup$

Using basic facts about cardinality, we can reduce the problem to finding a map $h:\mathbb{Q} \to \mathbb{N}$ such that $h(x) = n$ has infinitely many solutions for every $n\in \mathbb{N}$.

Let $g: \mathbb{Q} \to \mathbb{N}$ be any bijection between $\mathbb{Q}$ and $\mathbb{N}$. Let $h:\mathbb{Q} \to \mathbb{N}$ be the map that sends $\pm\frac{a}{b} \to a$ where $\frac{a}{b}$ is in lowest terms. Then the map $h\circ g^{-1}$ satisfies the desired properties.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.