4
$\begingroup$

Consider the functions $f(x)=2x+1$ and $g(x)=3x+1$, as well as their inverses f'(x) and g'(x). Starting with the number 1, is it possible to reach every positive integer through some finite sequence of these $4$ functions?

For example, we could have the following sequence:

$$1\,\,\overbrace {\longrightarrow}^{f(x)} \,\, 3\,\,\overbrace {\longrightarrow}^{f(x)} \,\,7\,\,\overbrace {\longrightarrow}^{g'(x)} \,\,2\,\,\overbrace {\longrightarrow}^{f(x)} \, \,5$$

Edit: I've tried a few things like taking base 6 and simply bashing a lot, and it seems like that it is possible, though I have no idea how to rigorously prove that.

$\endgroup$
  • $\begingroup$ What happens if you apply f'(x) or g'(x) to a number that doesn't invert? $\endgroup$ – Q the Platypus Mar 10 '17 at 1:53
  • 2
    $\begingroup$ Are you only allowed to apply $f'$ and $g'$ when the result is a natural? If $n$ is the smallest number that cannot be reached, we must have $n \equiv 2 \pmod 6$, as we can apply $f'$ to $1,3,5 \pmod 6, g'$ to $4 \pmod 6$ and $g'f$ to $0 \pmod 6$ and get a smaller number. I haven't found a way to make $8$. $\endgroup$ – Ross Millikan Mar 10 '17 at 1:53
  • $\begingroup$ Yes; you can only use the inverses when the output will be a positive integer. Thank you editors! $\endgroup$ – user386867 Mar 10 '17 at 1:55
  • $\begingroup$ 1, 4, 13, 27, 55, 18, 37, 12, 25, 8 is one way to reach 8 I believe. $\endgroup$ – user386867 Mar 10 '17 at 2:00
  • $\begingroup$ @A.Smith Sorry for asking here: why did you cancel your recent question about triangles (math.stackexchange.com/questions/2180126/…)? It looked interesting to me. $\endgroup$ – Aretino Mar 15 '17 at 21:36
2
$\begingroup$

Following on Ross Millikan's comment, if $t=6k+2$, then $f'\circ g'\circ g'\circ f\circ f\circ g$ takes $t$ to $4k+1$, so by induction there can be no minimum and hence all can be reached.

EDIT: The idea behind, of course, is that if $6k+2$ were the smallest number that could not be reached, then we could reach $4k+1$. But the reverse composition, ie, $f\circ g\circ g\circ f'\circ f'\circ g'$, takes $4k+1$ to $6k+2$, contradicting the assumption that it could not be reached.

For completeness sake, let's put it all in one place. Ross's comment is as follows:

If $n$ is the smallest number that cannot be reached, we must have $n\equiv2\pmod6$, as we can apply $f′$ to $1,3,5\pmod6$, $g′$ to $4\pmod6$ and $g′f$ to $0\pmod6$ and get a smaller number.

$\endgroup$
  • $\begingroup$ Well done. By following through the numbers, one can prove that all the primed functions can be applied. $\endgroup$ – Ross Millikan Mar 10 '17 at 3:02
  • $\begingroup$ Could this solution be stated by simply showing that each residue modulo 6 can be turned into a smaller number via the correct sequence of functions (i.e. just stating the 6 cases)? Or is it necessary to include the clause "If $n$ is the smallest number that cannot be reached, we must have $n\equiv2\pmod6$"? $\endgroup$ – user386867 Mar 10 '17 at 3:10
  • $\begingroup$ No, just showing that each residue class can't contain the smallest number is fine (actually better I suppose). Ross's statement was made when we did not yet know if there was or wasn't smallest number. $\endgroup$ – Fimpellizieri Mar 10 '17 at 3:25
  • $\begingroup$ @RossMillikan You definitely did most of the work. Thank you! $\endgroup$ – Fimpellizieri Mar 10 '17 at 3:25

Your Answer

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