Let n be an odd positive integer.Let M be a set of $n$ positive integers ,which are 2x2 different. A set $T$ $\in$ $M$ is called "good" if the product of its elements is divisible by the sum of the elements in $M$, but is not divisible by the square of the same sum. Given that $M$ is "good",how many "good" subsets of $M$ can there be?
Problem
Source:
Tags: number theory
14.04.2018 21:53
I can't understand the question, what is "2x2 different."
14.04.2018 21:58
No two of them are equal
22.02.2019 05:56
What does 2*2 mean? matrix?
21.03.2019 01:27
Any solution?
29.08.2019 14:50
Lamp909 wrote: Let n be an odd positive integer.Let M be a set of $n$ positive integers ,which are pairwise different. A set $T$ $\in$ $M$ is called "good" if the product of its elements is divisible by the sum of the elements in $M$, but is not divisible by the square of the same sum. Given that $M$ is "good",how many "good" subsets of $M$ can there be? Official solution: Let $M=\{a_1,a_2,\dots a_n\}$ Claim: There are at most $2^{n-1}$ good subsets of $M$. Proof: Let $A$ be a good subset of $M$, if $M\setminus A$ is good then this would imply that \begin{align} \sum_{a_i \in M}a_i & \mid \prod_{a_i \in A} a_i \\ \sum_{a_i \in M} a_i & \mid \prod_{a_i \in M\setminus A}a_i \end{align}Then, multiplying $(1)$ and $(2)$ we get that $\left(\sum_{a_i \in M}a_i\right)^2\mid \prod_{a_i \in M}a_i$, but this contradicts the fact that $M$ is good, so at least one of $A$ and $M\setminus A$ is good, wich proves the claim. To show that $2^{n-1}$ is achievable, we take $n=2k+1$, and $p$ a prime such that $p>\frac{n(n-1)}{2}$. Now we take $a_i=pi$ for $1\leq i\leq n-1$ and $a_n=p^{k+1}-p\frac{n(n-1)}{2}$ then we have that $a_1+a_2+\dots+a_n=p^{k+1}$, and then all subsets with more than or exactly $k+1$ elements are good, and there are exactly $2^{n-1}$ of them.