1

For each integer $n$, $p(n)$ outputs an ordered pair whose members are remainders of $n$ when divided by $4$ and $6$ respectively.
So $$p(n) = (n \mod 4, n \mod 6). $$ If ten thousand integers are chosen at random, how many can you say for certain must have the same value for $p$?

I did a similar example where instead of $4$ and $6$, it was $3$ and $4$.
The solution was just $\lceil \frac{10000}{3\times 4}\rceil = 834$.
However, my solution says it is not the same methodology for when it is $4,6$. How come? How would I do this?

(I determined the easier solution by looking at residues $\mod 3$ and residues $\mod 4$.)

OneGapLater
  • 820
  • 1
  • 9
  • 22
  • 1
    It's not the same (exact) solution for $4$ and $6$ because $4$ and $6$ share a factor $2$, which means that the two components of $p(n)$ must either both be even or both be odd. So, for instance, $p(n) = (2, 3)$ is impossible. – Arthur Oct 13 '17 at 10:09
  • Ah I see, how do you see it is impossible? Also, how do we see that with $3,4$ each combination is possible? – OneGapLater Oct 13 '17 at 10:10
  • As I said, it all comes down to the fact that $4$ and $6$ shares a factor, while $3$ and $4$ does not. – Arthur Oct 13 '17 at 10:12
  • Oh I see. How about if we instead replaced it with $k,3k$ for any $k\in\mathbb{N}$? What restrictions do we get on the outputs of $p$? – OneGapLater Oct 13 '17 at 10:13
  • 1
    If we have the map $p_k(n) = (n\mod k, n\mod 3k)$, you mean? Then only pairs one of the forms $(i, i)$, $(i, i+k)$ and $(i, i+2k)$ are possible. In general, if we have the map $q(n) = (n\mod a, n\mod b)$ and $\gcd(a, b) = d$, then the pair $(i, j)$ is possible to reach iff $i-j$ is divisible by $d$. – Arthur Oct 13 '17 at 10:17
  • Ah I see, so it all comes down to the $\gcd$ of the two numbers which will give us the number of pigeonholes (since it determines how many solutions there are). Curious: is there a good proof for your general case? – OneGapLater Oct 13 '17 at 10:25
  • 1
    If you take the least common multiplier of $4$ and $6$ (instead of the product), so $12$ instead of $24$, everything is fine. The reason is that the remainder modulo $12$ already determines the remainders modulo $4$ and $6$. This can be generalized. – Peter Oct 13 '17 at 10:30

0 Answers0