5. В лагерь приехало 100 мальчиков и несколько девочек. Оказалось, что все девочки имеют поровну знакомых среди мальчиков, а никакие двое мальчиков не имеют поровну знакомых среди девочек, хотя каждый мальчик знаком хотя бы с одной девочкой. Кроме того, Петя знаком со всеми девочками. Какое наименьшее количество девочек могло приехать в лагерь?

Пусть приехало n девочек. У каждого мальчика число знакомых среди девочек — целое от 1 до n. Эти числа у 100 мальчиков попарно различны, значит, n должно быть не меньше 100.

Обозначим через k общее для всех девочек число знакомых мальчиков. Тогда число всех пар «знакомые мальчик и девочка» равно nk, поэтому сумма чисел знакомых у мальчиков должна делиться на n.

При n = 100 степени знакомости мальчиков обязаны быть числами от 1 до 100. Их сумма равна 5050, которая на 100 не делится. Значит, 100 девочек недостаточно.

При n = 101 Петя имеет 101 знакомую девочку, а остальные 99 мальчиков должны иметь попарно различные степени из чисел от 1 до 100. Пусть пропущенное число — x. Сумма степеней всех мальчиков равна 5151 − x = 51 · 101 − x. Для делимости на 101 потребовалось бы, чтобы x делилось на 101, что невозможно при 1 ≤ x ≤ 100.

Покажем, что 102 девочки возможны. Пусть Петя знаком со всеми 102 девочками, а степени знакомости остальных мальчиков — все числа от 1 до 101, кроме 1 и 50. Это 99 различных положительных чисел. Сумма степеней всех мальчиков равна 102 + (1 + 2 + … + 101 − 1 − 50) = 5202 = 102 · 51.

Такое распределение знакомств между мальчиками и девочками существует: степени мальчиков не превосходят 102, а у каждой из 102 девочек можно задать степень 51. Для этих последовательностей степеней условие существования двудольного графа выполняется: для любого числа r мальчиков при r ≤ 51 сумма их степеней не больше 102r, а при r ≥ 51 — не больше общей суммы 5202. Следовательно, можно устроить знакомства так, чтобы каждая девочка знала ровно 51 мальчика.

Ответ: 102 девочки.