Для начала проясним, что называют приведением дроби к новому знаменателю.
Из основного свойства дроби следует, что любая обыкновенная дробь a/b имеет бесконечно много равных ей дробей, которые получаются при умножении числителя и знаменателя исходной дроби на любое натуральное число m. Таким образом, любую обыкновенную дробь a/b мы можем заменить равной ей дробью с большим числителем и знаменателем вида . Так от исходной дроби мы можем перейти к дроби с новым знаменателем.
Теперь интуитивно понятно, что подразумевает приведение дроби к новому знаменателю. Привести дробь к новому знаменателю – это значит умножить числитель и знаменатель исходной дроби на некоторое натуральное число m, в результате получается дробь с новым знаменателем, причем она равна исходной дроби.
Рассмотрим пример. Пусть дана обыкновенная дробь 11/25, и ее нужно привести к новому знаменателю. Умножим числитель и знаменатель этой дроби на 4. Так как 11·4=44 и 25·4=100, то после умножения мы получим дробь 44/100. В итоге дробь 11/25 приведена к дроби с новым знаменателем вида 44/100. Весь процесс принято записывать в виде следующей цепочки равенств: .
Понятно, что исходную дробь можно привести к множеству разных знаменателей (если бы в рассмотренном выше примере мы провели умножение не на 4, а на другое число, то мы бы пришли к дроби с другим знаменателем). Но новым знаменателем данной дроби могут быть не все числа. Новыми знаменателями дроби a/b могут быть лишь числа b·m, кратные числу b (смотрите делители и кратные). Числа, не кратные числу b, не могут быть новыми делителями дроби.
Пусть сотрудников 101 или меньше. Упорядочим их по убыванию оставшегося размера выплаты. Будем распределять монеты так:
Заплатим первому в очереди 1 монетой максимального номинала из имеющихся, а затем поставим его в очередь согласно оставшемуся размеру выплаты.
Почему это сработает: если максимальный номинал монеты x >= 3, то осталось выплатить не меньше, чем 100*(1+2+3+...+(x-1))+x = 50x^2-49x, у первого в очереди остаток к выплате не меньше, чем (50x^2-49x)/101 >= x.
Если x = 2, то первому в очереди надо выплатить не меньше 2 тугриков, поскольку в противном случае сумма всех монет была бы не больше 101 (не более 101 человека, каждому надо выплатить не более 1 тугрика), но сумма всех монет не меньше, чем 100*1 + 2 = 102.
Если x = 1, то очевидно, выплатить получится.