number theoretical questions for division of numbers $1$ to $100$

Question

Suppose we have a directed bipartite graph with $100$ vertices on both sides, and both consist of numbers $1$ to $100$. There is an arc $(i,b)$ from the left to the right side if and only if $i$ divides $b$. There are three questions:

1. Which pairs of vertices have at least $5$ neighbors in common (i.e. which pairs of vertices divide at least $5$ same numbers)?

2. How many arcs are there in total?

3. Take all possible combinations of vertices (single vertices, pairs, triples, etc) with at least $5$ neighbors in common. Find the maximal such sets.

Answers:

1. I guess here we have to count what each pair of numbers divides, so we have the number $\lfloor \frac{100}{\mathrm{lcm}(i,j)}\rfloor $. We first count how many numbers divide at least $5$ numbers on their own and that is $\lfloor \frac{100}{i}\rfloor \geq 5$. Here we see that $i\leq 20$. So we would have to look at ${20\choose 2}$ pairs. Another condition is that $\mathrm{lcm}(i,j) \leq 20$ but I do not know how to continue here to write the exact pairs? I guess each number and its multiples until $20$ is included, but there are some pairs such as $(2,3)$ which also appear.

2. I figured out the second question by counting how many divisors a number $b$ on the right has. From $1$ to $100$ we sum up $\lfloor \frac{100}{i}\rfloor $ and I get the total $482$.

3. I wrote a code to calculate these maximal sets, and I know the answer is $$(1, 17), (1, 2, 3, 6, 9, 18), (1, 19), (1, 2, 4, 5, 10, 20), (1, 3, 5, 15), (1, 2, 4, 8, 16), (1, 13), (1, 2, 7, 14), (1, 2, 3, 4, 6, 12), (1, 11).$$ I am not sure how to prove it mathematically. It should be a generalization of the first question. I guess we would use the lcm again and for example the fact that some numbers are prime so they could not be contained in larger sets.

Any help is appreciated.

Answer 1

1. Which pairs of vertices have at least 5 neighbors in common (i.e. which pairs of vertices divide at least 5 same numbers)?

The question in the parentheses only counts the pairs on the left side with five common neighbours. In other words, it only deals with out-neighbours. If you would like to find pairs with five common in-neighbours as well, you have to also find pairs that have at least five common divisors.

The former is, as you say, equivalent to finding pairs $(i,j), 1 \leq i < j \leq 100$ with $\text{lcm}(i,j) \leq 20$. There seem to be $56$ such pairs and they are easy to find by programming (and indeed easy, but tedious, to write out by hand).

The latter is equivalent to finding pairs $(i,j), 1 \leq i < j \leq 100$ such that $\text{gcd}(i,j)$ has at least five divisors. My computer says that there are $71$ such pairs.

This comes out to a grand total of $127$ pairs. But unless this was a programming assignment, I think the question was only aimed at giving a characterization of pairs with at least $5$ common neighbours (which we have done in terms of their $\text{lcm}$ and $\text{gcd}$).

2. How many arcs are there in total?

Your approach is sound and my computer says $482$ as well.

3. Take all possible combinations of vertices (single vertices, pairs, triples, etc) with at least 5 neighbors in common. Find the maximal such sets.

As in the first part, a set of numbers is valid if and only if the least common multiple $m$ of all the elements is at most $20$. Also notice that if $m \leq 20$, then we can add it to the set to get another valid set, and we can also add every divisor of $m$, since this doesn't increase the lowest common multiple of the members. This means that the maximal sets must be of the form $\{i : i \text{ divides } m\}$.

Finally, if this number $m$ was at most $10$, then we could also add $2m$ to the set to get a larger one. So in the end the maximal combinations are the sets of divisors of $m$ for $11 \leq m \leq 20$, and these are exactly the ones you gave in your answer.