Первое решение. Заплатив монету перед первым взвешиванием, мы имеем $99$ монет, среди которых есть хотя бы одна настоящая. Положим на две чаши весов по одной монете. Если одна из них перевешивает, то она настоящая. Если же весы в равновесии, то либо обе взвешиваемые монеты настоящие, либо обе фальшивые. Заплатив одну из них, мы имеем $98$ монет, среди которых есть хотя бы одна настоящая. Продолжив так далее, либо на следующем шаге обнаружим настоящую монету, либо будем иметь $97$ монет, среди которых есть хотя бы одна настоящая. Если все время весы будут показывать равновесие, то в конце концов будем иметь две монеты, среди которых есть хотя бы одна настоящая. Положим на две чаши весов по одной монете. Если одна из них перевешивает, то она настоящая. Если же весы в равновесии, то обе оставшиеся монеты настоящие.

Второе решение. Сначала покажем, что за два взвешивания можно найти группу из $33$ монет, в которой есть настоящая.
Разделим монеты на $3$ группы $A$, $B$, $C$ по $33$ монеты и одну в остатке. Заплатив этой монетой, сравним группы $A$ и $B$ (заметим, что хотя бы одна настоящая монета еще осталась). Если весы не остались в равновесии, то на перевесившей чашке есть хотя бы одна настоящая. Если же весы в равновесии, то сравним группы $A$ и $C$, заплатив монетой из $B$. Если одна перевесила, то в ней есть настоящая, а если весы в равновесии, то в каждой из групп $A$, $B$, $C$ было поровну настоящих монет — значит, хотя бы по одной. Тогда в группах $A$ и $C$ осталось по настоящей монете.
Итого, мы нашли группу (назовем ее $D$) из $33$ монет, в которой есть настоящая; кроме этой группы, у нас осталось еще хотя бы $65$ монет (пусть они образуют группу $E$). Теперь сравним одну монету из группы $D$ с каждой из остальных монет этой группы (платя каждый раз монетами из $E$). Тогда либо какая-то монета перевесит (она и будет настоящей!), либо все монеты будут весить поровну. В последнем случае, так как в $D$ есть настоящая, то все монеты в $D$ будут настоящими. В любом случае мы нашли хотя бы одну настоящую монету.