3
$\begingroup$

|$S = \{1,2,3,...,2018\}$ and $M \subseteq S$, $\forall \{x,y,z\} \subseteq M, \: xy \ne z$. What is the maximum possible value for $M$?


Attempt:

Notice the possible sets satisfying $M$ include:

$$ \{1,2,3\}, \{1,2,5,6,11 \}, ... $$

Notice that $1$ can always be included. Now let us find the greatest $x(x+1)$ that is smaller than $2018$. We find that $44 \times 45$. Notice that both $$ A = \{ 1, 44, 46, ..., 2017, 2018 \}, \:\: \text{and } B = \{1, 45, 46, ..., 2017, 2018 \} $$

satisfy $M$. The cardinality is $1975$. I am quite sure that these are the only sets satisfying $M$ with cardinality of $1975$.

Now consider set $C = \{2,3,4,...,42,43\}$. If I can show that $A$ and $B$ are the only sets with cardinality $1975$, and then showing that adding an element from $C$ to $A$ or $B$ will lead to violation of $M$, then $max(|M|)=1975$.

Now if there is another set with cardinality $1975$ other than $A$, $B$, let it be $X$. We can form an $X$, either by switching elements of $A$ with $C$, or of $B$ with $C$. Now switching one element of $A$ (one that includes $2$):

$$ \{ 1, 44, 46, ..., 2018 \} \rightarrow \{1, 2, 46, ..., 2018 \}$$

then we must also replace $46 \: or \: 2(46)$, $47 \: or \: 2(47)$, ..., and $1009 \: or \: 2018$, in total there are $1009 - 45 > |C|$ to be replaced, so it is not possible.

Now another example (includes $3$):

$$ \{ 1, 44, 46, ..., 2018 \} \rightarrow \{1, 3, 46, ..., 2018 \}$$

then we must also replace $46 \: or \: 3(46)$, $47 \: or \: 3(47)$, ..., and $672 \: or \: 2016$, in total there are $672 - 45 > |C|$ to be replaced, so it is also not possible.

Now let us consider the one that includes $43$.

$$ \{ 1, 44, 46, ..., 2018 \} \rightarrow \{1, 43, 46, ..., 2018 \}$$

then we must only replace $43(46), \: or \: 46$. But if we do replace one, it must be with one from $\{2,3,...,42\}$, and we will see that eventually we will have to replace more elements. (Now I have difficulty explaining this part)

Is my approach efficient and clear? are there better approaches?


I have another approach. We have found that $max(|M|)\ge 1975$. Instead of searching the maximum, let us consider

$$ A = \{ 1,45, 46, ..., 2017,2018 \}, \: \: B= \{44\} $$ $$ C = \{2,3,4, ..., 41,42,43 \} $$

we need to show that the minimum number of elements we must take from $S=A \cup B \cup C$ so that the new set satisfy $M$ is $43$.

Now if we clear $B \cup C$, then we just eliminate $43$ numbers such that the new set satisfy $M$. We will show that we cannot eliminate $42$ elements such that the result satisfy $M$. Now assume the contrary: among the 42 numbers, if all of them are from $C$, then we know this cannot be done because $44$ is troublesome. Now, we can write $$ 42 = \alpha + \beta, \:\: 1 < \alpha, \beta < 42 $$ where $\alpha$ is the number of elements from $C^{c}$ and $\beta$ is number of elements from $C$.

Notice that for each $x \in C$ it has at least two elements in $A$ (call it $a_{1}, a_{2}$) such that $xa_{1}, x a_{2} \in A$. $43$ has 2 "troublesome" numbers in $A$ ($43 \times 45, 43 \times 46$), $42$ has 4 "troublesome", $41$ has 5 "troublesome", and so on .. adding 1 more "troublesome".

  • If $\alpha =1, \beta = 41$, then there is one element left in $C$ such that it has at least two elements in $A$ that is "troublesome". Thus even if $\alpha =1$ means that one of the "troublesome" is cleared, there will still be at least one "troublesome" left. Also notice that we have not cleared the troublesome 44.

    • If $\alpha =2, \beta = 40$, we must substract $1$ from $\alpha$ to clear 44. Then the remaining $1$ is from $A$ and by similar reasoning we will still have "troublesome" left.

    • If $\alpha =3, \beta = 39$, we must substract $1$ from $\alpha$ to clear 44. Then the remaining $2$ is from $A$. We have $3$ numbers from $C$ which in total have at least $4$ "troublesome" in $A$. Thus the cleared $2$ elements from $A$ is still not enough.

    • .... We can see that it is not possible to clear $42$ elements or less from $S$ so that the remaining will satisfy $M$.

Thus we have shown that $max(|M|) \le 1975$. So the answer is $max(|M|)=1975$.

$\endgroup$
  • $\begingroup$ You want max value of $|M|$ right? Also, you should clarify if $x,y,z$ are distinct (in some setups, they need not be). $\endgroup$ – Calvin Lin Nov 13 '19 at 10:51
  • $\begingroup$ There are actually 3 optimal $M$, the complements in $S$ of: $$\{2,3,\dots,44\} \\ \{2,3,\dots,43,45\} \\ \{2,3,\dots,43,1980\} $$ $\endgroup$ – RobPratt Nov 14 '19 at 19:12
2
$\begingroup$

(second approach)

Much better. You avoid the "Assume that the set $M$ obeys some construction property" and work with a general $M$ instead.

Still have some issues:

  • How do you know the troublesome numbers do not overlap in a manner that allows us to cancel it out? E.g. If 43, 42, 41, 40 map into a set of "three troublesome elements" , we can simply remove these three and be done.

You can tweak this approach to work. I strongly recommend thinking it over first, before reading the hidden text.

Set $A = \{1, 45, 47, \ldots, 2018\}$, $B = \{2, 3, \ldots, 44\}$.
CRUX: Fix $b = 45-k \in B$ and show that it has (at least) $k$ mutually distinct troublesome pairs $\{a_i, ba_i\} \subset A $, namely $a_i = 44+i$. So if $b \in M$, then we have to remove at least $k$ numbers from $A$.
Then, if $|M| = 1975+n$, $ |M\cap B | =k > 0$ so $min (M \cap B) \geq 45-k$ which implies $|M \cap A | \leq 1975 -k $, contradicting $|M| > 1975$.


(first approach)

Your approach is currently not correct. In particular, simply showing "showing that adding an element from $C$ to $𝐴$ or $𝐵$ will lead to violation of 𝑀" is not valid.

For example, you did not rule out the possibility of "adding 2 elements from $C$ but removing an element from $A$", which would increase the size by 1.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $|X|$ must be $1975$ $\endgroup$ – Arief Anbiya Nov 13 '19 at 10:59
  • $\begingroup$ I am not disagreeing (as yet) that "max $|M| = 1975$. I'm claiming that your proof isn't watertight (as yet) and that you will not receive the full score of it. If the grader is nitpicky, this might be a $0^+$ solution. $\endgroup$ – Calvin Lin Nov 13 '19 at 11:02
  • $\begingroup$ I add another approach in my post.. $\endgroup$ – Arief Anbiya Nov 14 '19 at 9:33
  • $\begingroup$ I've added comments. $\endgroup$ – Calvin Lin Nov 14 '19 at 15:42
  • $\begingroup$ @AriefAnbiya I took a quick look, and my main advice is to work on the phrasing. E.g. 1) What does "We can form M' by considering it as the union of two disjoint sets satisfying M, A' and X,..." really mean? 2) What is an enemy?(You never defined this, and suddenly used it in a lemma. Yes, I can figure it out from the context, but can everyone else?) 3) I personally found it very hard to continue reading after that 4) $43-k$ has $k+2$ enemies right? So, even what you're saying here doesn't match up ... $\endgroup$ – Calvin Lin Dec 14 '19 at 15:26
0
$\begingroup$

Here's an alternative approach, admittedly unsuitable for a pencil-and-paper contest setting, to certify 1975 as an upper bound. For $s\in S$, let binary decision variable $x_s$ indicate whether $s$ appears in $M$. Also let $T=\{(i,j,ij)\in S^3: i<j\}$. The problem is to maximize $\sum_{s \in S} x_s$ subject to: $$ \sum_{s\in\{i,j,k\}} x_s \le 2 \quad \text{for $(i,j,k)\in T$}. $$ Now relax integrality and consider the dual linear programming (LP) problem, which is to minimize $$2\sum_{(i,j,k)\in T} u_{i,j,k} + \sum_{s\in S} v_s$$ subject to: \begin{align} \sum_{\substack{(i,j,k)\in T:\\ s\in\{i,j,k\}}} u_{i,j,k} + v_s &\ge 1 &&\text{for $s\in S$}\\ u_{i,j,k} &\ge 0 &&\text{for $(i,j,k)\in T$}\\ v_s &\ge 0 &&\text{for $s\in S$} \end{align} By weak LP duality, any dual feasible solution $(u,v)$ provides an upper bound for the original problem. Taking $u_{i,j,k}=1$ for the following set $T^*$ of 168 triples $(i,j,k)$ and $v_s=1$ for $s\in S \setminus \cup_{(i,j,k)\in T^*} \{i,j,k\}$ yields dual objective value $2\cdot 168+ 1639=1975$, as desired: $$\{(2,673,1346),(2,677,1354),(2,683,1366),(2,691,1382),(2,701,1402),(2,709,1418),(2,719,1438),(2, 727,1454),(2,733,1466),(2,739,1478),(2,743,1486),(2,751,1502),(2,757,1514),(2,761,1522),(2,769, 1538),(2,773,1546),(2,787,1574),(2,797,1594),(2,809,1618),(2,811,1622),(2,821,1642),(2,823,1646 ),(2,827,1654),(2,829,1658),(2,839,1678),(2,853,1706),(2,857,1714),(2,859,1718),(2,863,1726),(2 ,877,1754),(2,881,1762),(2,883,1766),(2,887,1774),(2,907,1814),(2,911,1822),(2,919,1838),(2,929 ,1858),(2,937,1874),(2,941,1882),(2,947,1894),(2,953,1906),(2,967,1934),(2,971,1942),(2,977, 1954),(2,983,1966),(2,991,1982),(2,997,1994),(2,1009,2018),(3,509,1527),(3,521,1563),(3,523, 1569),(3,541,1623),(3,547,1641),(3,557,1671),(3,563,1689),(3,569,1707),(3,571,1713),(3,577,1731 ),(3,587,1761),(3,593,1779),(3,599,1797),(3,601,1803),(3,607,1821),(3,613,1839),(3,617,1851),(3 ,619,1857),(3,631,1893),(3,641,1923),(3,643,1929),(3,647,1941),(3,653,1959),(3,659,1977),(3,661 ,1983),(4,409,1636),(4,419,1676),(4,421,1684),(4,431,1724),(4,433,1732),(4,439,1756),(4,443, 1772),(4,449,1796),(4,457,1828),(4,461,1844),(4,463,1852),(4,467,1868),(4,479,1916),(4,487,1948 ),(4,491,1964),(4,499,1996),(4,503,2012),(5,337,1685),(5,347,1735),(5,349,1745),(5,353,1765),(5 ,359,1795),(5,367,1835),(5,373,1865),(5,379,1895),(5,383,1915),(5,389,1945),(5,397,1985),(5,401 ,2005),(6,293,1758),(6,307,1842),(6,311,1866),(6,313,1878),(6,317,1902),(6,331,1986),(7,257, 1799),(7,263,1841),(7,269,1883),(7,271,1897),(7,277,1939),(7,281,1967),(7,283,1981),(8,227,1816 ),(8,229,1832),(8,233,1864),(8,239,1912),(8,241,1928),(8,251,2008),(9,211,1899),(9,223,2007),( 10,191,1910),(10,193,1930),(10,197,1970),(10,199,1990),(11,173,1903),(11,179,1969),(11,181,1991 ),(12,157,1884),(12,163,1956),(12,167,2004),(13,149,1937),(13,151,1963),(14,137,1918),(14,139, 1946),(15,127,1905),(15,131,1965),(16,64,1024),(17,99,1683),(18,81,1458),(19,68,1292),(20,71, 1420),(21,66,1386),(22,76,1672),(23,77,1771),(24,55,1320),(25,79,1975),(26,63,1638),(27,74,1998 ),(28,70,1960),(29,69,2001),(30,65,1950),(31,62,1922),(32,61,1952),(33,52,1716),(34,56,1904),( 35,57,1995),(36,54,1944),(37,51,1887),(38,53,2014),(39,49,1911),(40,50,2000),(41,47,1927),(42, 48,2016),(43,46,1978),(44,45,1980)\} $$

| cite | improve this answer | |
$\endgroup$

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.