Решение задачи 374

Условие:

В стране Далекой провинция называется крупной, если в ней живет более 7% жителей этой страны. Известно, что для каждой крупной провинции найдутся две провинции с меньшим населением такие, что их суммарное население больше, чем у этой крупной провинции. Какое наименьшее число провинций может быть в стране Далекой?

Решение:

Оценка:

Отсортируем страны по количеству жителей и пронумеруем их до 1 до n. Рассмотрим самую маленькую крупную провинцию. Из условия следует, что есть еще минимум две некрупных провинции. Напишем сколько максимум может быть процентов жителей в i-ой стране, учитывая, что a_k+a_{k+1} ≥ a_{k+2}, m≤k≤n−2, где m -- номер наименьшей крупной провинции:

В первой: 7%
В второй: 7%
В третьей: 14%
В четвертой: 21%
В пятой: 35%

Так как 7+7+14+21+35 < 100, получаем, что стран минимум 6.

Пример:

Приведем пример шести, удовлетворяющие условию: 7%, 7%, 13%, 19%, 27%, 27%.

Замечание: В оценке мы предположили, что крупная страна есть, но если их нет, то провинций хотя бы 15.

Ответ: 6.