MathDB
100 states that are in dispute on planet Mars

Source: II - Rioplatense 1992 L3 P4

September 19, 2022
combinatorics

Problem Statement

On the planet Mars there are 100100 states that are in dispute. To achieve a peace situation, blocs must be formed that meet the following two conditions: (1) Each block must have at most 5050 states. (2) Every pair of states must be together in at least one block. Find the minimum number of blocks that must be formed.