A set $S=\{ s_1,s_2,...,s_k\}$ of positive real numbers is "polygonal" if $k\geq 3$ and there is a non-degenerate planar $k-$gon whose side lengths are exactly $s_1,s_2,...,s_k$; the set $S$ is multipolygonal if in every partition of $S$ into two subsets,each of which has at least three elements, exactly one of these two subsets in polygonal. Fix an integer $n\geq 7$. (a) Does there exist an $n-$element multipolygonal set, removal of whose maximal element leaves a multipolygonal set? (b) Is it possible that every $(n-1)-$element subset of an $n-$element set of positive real numbers be multipolygonal?
Problem
Source: Romania TST 2016 Day 5 Problem 3
Tags: combinatorics
bobthesmartypants
02.06.2016 06:10
$S$ is polygonal if and only if $2\max\{s_1, s_2, \ldots , s_k\} < s_1+s_2+\cdots +s_k$.
I'll edit this post if I get time after finishing up finals stuff.
Consider the set $S$ of size $n$ defined as $S=\{2,4, \ldots ,2^{n-4}, 2^{n-3}, 2^{n-3}, 2^{n-3}, 2^{n-2}-1\}$. When this set is divided into two pieces either one set has three $2^{n-3}$'s, or one set has two $2^{n-3}$'s. In addition, that set can either have $2^{n-2}-1$ or not have it. No matter which of the 4 cases, it is easy to see that set is polygonal by the above hidden observation. The other set is not polygonal because it only contains distinct powers of two or near powers of two, and so by the geometric series summation formula the sum of all except the largest element is smaller than the largest element always, so by the observation again it is not polygonal. Thus, this set is multipolygonal.
Now if we remove $2^{n-2}-1$ by almost identical logic the remaining set is also multipolygonal so this set works.
parmenides51
04.07.2019 21:24
It was also RMM Shortlist 2016 C3