Question

Наташа распределила рыбок по 27 аквариумам так, что в любых трех аквариумах плавает не менее 7 рыбок. Найдите наименьшее возможное чиcло рыбок.

Answer 1

В 3 аквариумах плавает 7*3 = 21 рыбка
В остальных 27 - 3 = 24 аквариумах может плавать сколько угодно рыбок.
Нам нужно знать наименьшее число рыбок, поэтому, пусть в 24 аквариумах плавает по 1 рыбки
Всего в 27 аквариумах плавает 21 + 24 = 45 рыбок.

Answer 2

Для нахождения наименьшего возможного числа рыбок, которое распределено по 27 аквариумам так, что в любых трех аквариумах плавает не менее 7 рыбок, можно воспользоваться методом жадного алгоритма.

Попробуем минимизировать число рыбок в каждом аквариуме. Пусть первые 18 аквариумов содержат по 7 рыбок каждый (минимальное значение для каждого аквариума, чтобы удовлетворить условию), тогда остается распределить оставшиеся рыбки в оставшиеся 9 аквариумов.

Если в 9 аквариумах будет по 6 рыбок, тогда количество рыбок составит: 18 аквариумов * 7 рыбок/аквариум + 9 аквариумов * 6 рыбок/аквариум = 126 + 54 = 180 рыбок.

Таким образом, наименьшее возможное число рыбок, удовлетворяющее условиям задачи, составляет 180 рыбок.