MathDB
The Attack and Defense of Snails

Source: 2024 imocsl C3 (Boring Competiton P3)

August 8, 2024
combinatoricsIMOC

Problem Statement

There are nn snails on the plane where the ii snail has aia_i attack and did_i defense, where ai,diRa_i, d_i\in \mathbb{R} and each snail has a distinct attack and a distinct defense. We said a 4-tuple of subsets of snails (S1,S2,S3,S4)(S_1, S_2, S_3, S_4) is balanced if S1+S3|S_1|+|S_3| is either n/2\lceil n/2\rceil or n/2\lfloor n/2\rfloor and there exist real numbers A,DA, D such that \begin{align*} S_1=\{i\ |\ a_i\geq A\text{ and } d_i\geq D, 1\leq i\leq n\}\\ S_2=\{i\ |\ a_ikk such that there is always at least kk balanced 4-tuples of subsets.
Proposed by redshrimp