How many pairs $(x,y)$ such that $x+y=n$ have an $x$ or $y$ divisible by 3 but $x$ and $y$ are not equal to 3?

61 Views Asked by At

Let the set $S_{n}$ = {$(x,y):x,y \in \mathbb{O}$} such that $x+y=n$ where $\mathbb{O}$ is set of odd integers > 1.

Let us define the function $f(n) = |S_{n}|$ that counts the number of pairs in $S_{n}$.

Examples: $S_{10} =\{(3,7),(5,5),(7,3)\}$ and $f(10) = 3$.

$S_{14} = \{(3,11), (5,9), (7,7), (9,5),(11,3)\}$ and $f(14) = 5$

$S_{32} = \{(3,29), (5,27), (7,25), (9,23), (11,21), (13,19), (15,17), (17,15), (19,13), (21,11), (23,9), (25,7), (27,5), (29,3)\}$

and $f(32) = 14$

It turns out that $f(n) = ((n/2) - 2)$.

Let us define another function $g(n)$ that counts the number of pairs $(x,y)$ such that either $x$ or $y$ is divisible by 3, but $x \neq 3$ and $y\neq 3$.

Example: $g(32) = 8$ because there are 8 pairs where $x$ or $y$ is divisible by 3 but not equal to 3. They are (5,27), (9,23), (11,21), (15,17), (17,15), (21,11), (23,9) and (27,5).

There are two cases: Case 1, $n$ is divisible by 3 and case 2, $n$ is not divisible by 3. Let us only consider case where $n$ is not divisible by 3, since if $n$ is divisible by 3, any pair where $x$ is divisible by 3, $y$ will also be divisible by 3.

What is the formula for $g(n)$ in terms of $f(n)$ for values of $n$ not divisible by 3?

What is the formula for $g(n)$ in terms of $f(n)$ for limit $n \to\infty$?

My guess is that as $n \to \infty$ for $n$ not divisible by 3, the value of $g(n)$ approaches $(2/3)f(n)$.

1

There are 1 best solutions below

0
On

The sum of $2$ multiples of $k$ is also a multiple of $k$. Therefore, if $n$ is not divisible by $3$, we know that the $\left\lfloor \frac{n}{6}\right\rfloor -1$ values of $p$ where $p$ is divisible by $3$ will not overlap any of the $\left\lfloor \frac{n}{6}\right\rfloor -1$ values of $q$ where $q$ is divisible by $3$.

So the formula for $g(n)$ in terms of $n$ for values of $n$ not divisible by $3$ is:

$$g(n)=2\left\lfloor \frac{n}{6}\right\rfloor -2$$

The formula for $g(n)$ in terms of $f(n)$ for values of $n$ not divisible by $3$ is:

$$g(n)=2\left\lfloor \frac{f\left(n\right)+2}{3}\right\rfloor -2$$

Your guess about the limit for $\frac{g(n)}{f\left(n\right)}$ is also right:

$$\frac{g(n)}{f\left(n\right)}=\frac{2\left\lfloor \frac{n}{6}\right\rfloor -2}{\frac{n}{2}-2}=\frac{\frac{n}{3}-2}{\frac{n}{2}-2}=\frac{2n-12}{3n-12}$$

$$\lim_{n\rightarrow\infty}\frac{2n-12}{3n-12}=\frac{2\infty-12}{3\infty-12}=\frac{2\infty}{3\infty}=\frac{2}{3}\left(\frac{\infty}{\infty}\right)=\frac{2}{3}$$