Let $n>1$ be an integer and $d_1<d_2<\dots<d_m$ the list of its positive divisors, including $1$ and $n$. The $m$ instruments of a mathematical orchestra will play a musical piece for $m$ seconds, where the instrument $i$ will play a note of tone $d_i$ during $s_i$ seconds (not necessarily consecutive), where $d_i$ and $s_i$ are positive integers. This piece has "sonority" $S=s_1+s_2+\dots s_n$. A pair of tones $a$ and $b$ are harmonic if $\frac ab$ or $\frac ba$ is an integer. If every instrument plays for at least one second and every pair of notes that sound at the same time are harmonic, show that the maximum sonority achievable is a composite number.
Problem
Source: 2022 Mexican Mathematics Olympiad P3
Tags: music, Divisors
01.12.2022 07:44
Lets make a $m$ x $m$ table where the line $i$ represents instrument $i$ and the columns represent seconds. If an instrument is playing at some second we can mark that cell, so now $s_i$ equals the amount of marked cells in the line $i$ and $S$ equals the sum of marked cells in each line. Notice that the sum of each column must equal the sum of each line, therefore if we maximize the amount of instruments playing at any given second we will achieve "maximum sonority". Let $n=p_1^{\alpha_1}p_2^{\alpha_2}....p_k^{\alpha_k}$ We will define a "Chain size" $C(k)$ as the sum of the exponents of the primes that compose $k$. That is if $k=p_1^{\beta_1}p_2^{\beta_2}....p_k^{\beta_k}$ than $C(k)=\beta_1+\beta_2+....+\beta_k$ Notice that $C(d_j)<C(n)$ for all $j<m$ Lemma 1: If $C(d_i)=C(d_j)$ with $i\neq j$ than $d_i$ and $d_j$ can't be harmonic. Proof: Suppose $d_i>d_j$ than for every prime $p$, $v_p(d_i)\ge v_p(d_j)$. Since $C(d_i)=C(d_j)$ than it must follow that in fact $v_p(d_i)=v_p(d_j)$ for every $p$ but that contradicts $d_i\neq d_j$ We propose that the maximum amount of instruments playing at any given second is $C(n)+1$ and that it is always achivable. First, notices that if $\alpha_1+\alpha_2+.....+\alpha_k + 2$ or more are playing than by pidgeon hole there will be at least 2 instruments $a$ and $b$ that are playing tones $d_a$ and $d_b$ respectively that have the same chain size, that is $C(d_a)=C(d_b)$ but by Lemma 1 they can't be harmonic. Now we propuse the next algorithm. At second $i$ play instrument $i$ for $m\ge i\ge2$. Let tone $d_i=p_1^{\beta_1}p_2^{\beta_2}....p_k^{\beta_k}$, play a tone $d_x$ such that $C(d_x)=C(d_i)+m$ by multiplying $d_i$ by an $m$ amount of $p_i$ such that $v_{p_i}(d_i)<v_{p_i}(n)$ and play a tone $d_y$ such that $C(d_y)=C(d_i)-r$ by dividing $d_i$ by an $r$ amount of $p_i$ such that $v_{p_i}(d_i)>0$. $d_x=d_i K$ and $d_y=\frac{d_i}{T}$ so $\frac{d_x}{d_y}=KT$ and so every instrument playing in the second $i$ is harmonic. More so, we are playing $C(n)+1$ instruments because we have chains sizes from $0$ all the way to $C(n)$. Therefore we can always play $C(n)+1$ instruments at any given second. The maximum sonority is $S=m(C(n)+1)$, which is composite. For seconds $1$ and $m$ just copy any other second. The algorithm is just to make sure that we play every instrument at least once.
17.01.2024 00:12
Let $S(h) = e_1 + e_2 + \cdots + e_k$ were $h = \prod_{i=1}^k p_i^{e_i}$ is its prime factorization. Note that two different harmonic tones cant have the same $S(h)$. Now consider the sonority in every second, because of what we said there are at most $S(n) + 1$ instruments playing (that is the number of different values of $S(h)$ were $h$ is a divisor of $n$) so the sonority of every second is at most $S(n) + 1$, then the sonority of all the piece is at most $m(S(n)+1)$. We can achieve the maximum in this way: Lets define a chain of $n$ as a secuence of numbers $n = a_1 \to a_2 \to \cdots \to a_{S(n)+1} = 1$ were $\frac{a_i}{a_{i+1}}$ is a prime number. We say that a chain of $n$ goes through $d$ (divisor of $n$) if $a_i = d$ for some $a_i$, its clear that every divisor $d$ of $n$ has a chain of $n$ going through $d$. At the second $s$ with $1 \leq s \leq m$, we construct a chain going through $d_s$ and turn those notes on. This assures that at every second there are $S(n) + 1$ instruments playing and that every instrument got played at least once. So the maximum achievable is $m(S(n)+1)$ which is clearly composite.