Is it possible for any finite group of people to choose a positive integer $N$ and assign a positive integer to each person in the group such that the product of two persons' number is divisible by $N$ if and only if they are friends?
Problem
Source: Baltic Way 2017 Problem 16
Tags: number theory, graph theory
11.11.2017 17:33
Sure. Initally give everyone the positive integer $1$. Choose some set of distinct primes $p_1,p_2,\dots,p_k$ where $k$ is the number of absent edges in the obvious graph. For the $i^{\text{th}}$ absent edge, multiply the value given to each person not incident to said absent edge by $p_i$. Take $N=p_1p_2\dots p_k$ for the result $\Box$ Edit: Some special care is required for the case with no friendships; take $N=2$ instead.
08.10.2021 21:48
Consider two different vertices $v_i,v_j$ that do not share an edge. Initially assign prime $p_{ij}$ to every vertex. Now, remove $p_{ij}$ from $v_i,v_j$. Do such operation with every other pair of vertices that do not share an edge. Take $N=\prod_{}p_{ij}$. Note that by construction, considering vertices $v_i,v_j$ that do not share an edge, the prime $p_{ij}$ is not represented in this edge. Consider vertices $v_i,v_j$ that do share an edge. Suppose there is a prime $p$ such that $p$ is not represented in this edge, then by construction it is possible only when $v_i,v_j$ do not share an edge, contradiction. We conclude product of numbers assigned to two vertices is divisible by $N$ if and only if those two vertices share an edge.
10.10.2021 07:46
Wow this is cute Let $n$ be the number of edges; consider $N = p_1p_2\ldots p_{n^2}$ where $p_{i}$ are distinct primes. Now, for any vertex $v_i$, we assign the set $a_i$ of primes. Rephrase the problem as the union of $a_i, a_j$ is $\{p_1\ldots p_{n^2}\}$ iff $i,j$ are adjacent. We will have the following conditions: $a_i$ can not have $p_{kn + i}$ for any integer $k$. For any $kn + i$, there is at most one vertex $v$ such that $a_v$ does not contain $p_{kn+i}$, furthermore, $v,i$ are not adjacent. Every vertex not adjacent to $v$ does not contain exactly one of $p_{kn+i}$ over all $k$. Now, we show that this works. For $i,j$ adjacent, clearly $a_i$ will contain every $p_{kn+j}$, and $a_j$ will contain every $p_{kn+i}$. Furthermore, for any $p_{kn+r}$, it will be contained in either $a_i$ or $a_j$. For $i,j$ not adjacent, there exists $k$ such that $p_{kn+j}$ is not in $a_i$ and, by the first condition, not in $a_j$ Therefore, this construction works.
10.10.2021 18:12
Take a collection P of $\binom{n}{2}$ primes. Let $N=\prod_{p\in P} p$. Initially set everyone's values to $N$. For each pair $i,j$, if they're friends, do nothing. If they aren't friends, divide both $i$ and $j$'s values by $p_{i,j}$. This clearly works because $i,j$'s product is divisible by $N$ if and only if for all primes $p$ $v_p(i)+v_p(j) \geq v_p(N)$, which happens only when $i,j$ are friends.