4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ You have looked at only one side of part $1$. The vertices on the side could share five neighbours too, if they had five common factors. For example, take $72$ and $54$ , which share all the common factors $1,2,3,6,9,18$. This will come down to their $\gcd$, though. $\endgroup$ Dec 5, 2020 at 10:15
  • $\begingroup$ In this case we were looking at a directed graph with arcs from left to right, although I agree it makes sense that we could look at the common factors. I am not sure if this would reduce cases though, because I do not see what conditions we could impose on the gcd? $\endgroup$
    – mandella
    Dec 5, 2020 at 10:53
  • 1
    $\begingroup$ Ah, sorry, I missed that it is directed. I will try to answer the question. $\endgroup$ Dec 5, 2020 at 11:34

1 Answer 1

3
+50
$\begingroup$
  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}$).

  1. How many arcs are there in total?

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

  1. 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.

$\endgroup$
4
  • $\begingroup$ Thank you for the answer. Your approach to count in-neighbors makes sense, but it wasn't required in this case as you mentioned. I do understand the part about the divisors inuitively but I am not sure how to write it mathematically. Maybe another sentence of explanation would help? $\endgroup$
    – mandella
    Dec 5, 2020 at 16:47
  • 1
    $\begingroup$ I edited my answer to be a bit more explicit - do tell me if you have further questions about it. $\endgroup$
    – Dániel G.
    Dec 5, 2020 at 17:12
  • $\begingroup$ Thank you for the great answer! $\endgroup$
    – mandella
    Dec 5, 2020 at 18:04
  • 1
    $\begingroup$ Good answer, was writing one but you've covered everything. +1 $\endgroup$ Dec 7, 2020 at 11:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.