0
$\begingroup$

If we have the set

$\Bigg\{ \frac{1}{1},\frac{1}{2},\frac{1}{3},...,\frac{1}{k} \Bigg\}=:A$

for some $k\in \mathbb{N}$ (known). We pick some $a\in \mathbb{Q}$ such that we have

$\Bigg\{ \frac{a}{1},\frac{a}{2},...,\frac{a}{k} \Bigg\}=:B$

The problem is, how do we pick the number $a\in \mathbb{Q}$ such that $a \neq k$ optimally so that the non-duplicates in the first and the second set are minimized i.e. $B$ shares as many elements as possible with $A$. By duplicates I refer to instances such as $\frac{1}{2}=\frac{2}{4}=\frac{4}{8}$ for example.

$\endgroup$
3
  • $\begingroup$ You first talk about minimizing duplicates, then maximizing the cardinality of the intersection. Those are opposite goals, as the duplicates of both sets make up the intersection. Minimizing seems easy (just choose a negative $a$, then the intersection is empty), so I assume you want maximize it. In that case, $a\neq 1$ makes sense, instead of the $a\neq k$ you mentioned. Can you edit/clarify what you mean? $\endgroup$
    – Ingix
    Commented Mar 22, 2021 at 9:06
  • $\begingroup$ My bad, I was trying to say that we need to minimize the number of elements in $B$ that are different from elements in $A$. I fixed it. $\endgroup$
    – user830143
    Commented Mar 22, 2021 at 9:39
  • $\begingroup$ This is the same problem as with $A = \{ 1, \dots, k \}$, and it might be easier to visualize this way. Then probably $a = 2$ or $a = \frac 1 2$ are the best choices. $\endgroup$
    – Hugo Manet
    Commented Mar 22, 2021 at 10:28

1 Answer 1

1
$\begingroup$

Hugo Manet has the right idea in his comment. I'll assume that the condition $$a \neq k$$ is actually $$a \neq 1,$$ as $a=1$ is the obvious solution with maximal intersection of $A$ and $B$, because then $A$=$B$.

First, $A$ is a $k$-element set, and the same is true for $B$ if $a \neq 0$. $a=0$ means $A \cap B =\emptyset$, so $a=0$ will never be the sole optimal solution, so we can forget about $a=0$. Similiarly, if $a<0$, we get $A \cap B =\emptyset$, so we can restrict ourselves to $a > 0$.

Let's consider an element $\frac1i \in A$, with $1 \le i \le k$. It can be equal to at most one $\frac{a}j \in B, 1 \le j \le k$. Similiarly, each $\frac{a}j \in B, 1 \le j \le k$ can b equal to at most one $\frac1i \in A$.

That means the cardinality of $A \cap B$ is the cardinality of

$$C_a=\{(i,j) \in \mathbb N^2, 1 \le i,j \le k \mid \frac1i=\frac{a}j\} = \{(i,j) \in \mathbb N^2, 1 \le i,j \le k \mid a =\frac{j}i\}.$$

Obviously, for each $i$ in the given range there can only be at most one $j$ in that range that fulfilles the qotient condition, and vice versa, so we have $|C_a| \le k$ with equality holding for the forbidden trivial case of $a=1$.

Also note that $C_a=C_{1/a}$, as this this just means transposing every pair $(i,j)$ into $(j,i)$. So we can concentrate on looking at $0 < a < 1$ cases, any solution here will have a corresponding solution $\frac1a$.

So let's assume

$$a=\frac{p}q,\, p,q \in \mathbb Z,\, p,q > 0,\, \gcd(p,q)=1,\, p < q$$

wich means we need to find $(i,j)$ such that

$$\frac{p}q=\frac{j}i \Longleftrightarrow pi=qj.$$

Since $q$ and $p$ have no common divisor greater than 1, that means $q|i$, so $i=fq$ for some integer $f \ge 1$. That means $j=\frac{pi}q=p\frac{i}q=fp \in \mathbb Z$. So if $q|i$, we can find a positive (since $f,p > 0$) integer $j=fp$ that makes $\frac{j}i=a$ come true.

In addition, if we assume $i \le k$ we get that $j = \frac{pi}q = i\frac{p}q < i \le k$, as we assumed $a=\frac{p}q < 1$.

So that means we know that for each $(i,j) \in C_a$, with $a=\frac{p}q < 1$ in reduced form, $q|i$ is a necessary condition, but also suffienct, as the corresponding $j=ai$ is an integer in the range $1 \le j \le n$.

That means

$$|C_a|=|\{i\in \mathbb N, 1\le i\le k : q|i \}|$$.

The cardinality if the second set above is easy to calculate, its simply $\lfloor\frac{k}q\rfloor$, which is maximized if $q$ is as low as possible, and for $a=\frac{p}q < 1$ in reduced form that happens when $q=2$, so $a=\frac12$.

It never gets better, though there are a few small $k$ cases where it's not the only optimum. For $k=1$, we get $|C_a|=0$ for all $a \neq 1$. For $k=2$ it's the only optimum. For $k=3$, $q=3$ also works, as $|C_{1/2}|=|C_{1/3}|=|C_{2/3}|=1$. For $k=4,5$ there are 2 even integers in the range $1\ldots k$, but only one divisble by $3$, so again $q=2$ is the only optimal value.

For $k=6$, both counts get upped by $1$ at the same time, so still $q=2$ is the only optimal value. In addition, as $6$ is divisible by both $2$ and $2$, the count for $q=3$ can never reach the count for $q=2$, as the count for $2$ always gets incremented earlier than the correpondig count for $3$.

To get the final answer:

For $k=1$, each $a\neq 1$ is qually bad, producing an empty intersection of $A$ and $B$.

For $k\ge 2$, $a=\frac12, a=2$ produce optimal solutions, with $|A \cap B|=\lfloor\frac{k}2\rfloor$.

Those are the only optimal solutions, except for $k=3$, where $a=\frac13, a=\frac23, a=\frac32, a=3$ also produce an optimal solution of $|A \cap B| =1$.

$\endgroup$

You must log in to answer this question.