Делимость на 3

Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.

Возможно эвристическое решение. Если выписать первые несколько чисел, то можно найти закономерность:
1 не делится
12 делится
123 делится
1234 не делится
12345 делится
123456 делится
1234567 не делится
12345678 делится

Эту последовательность можно проверить, продолжив и дальше. Таким образом, получается последовательность - + + - + + - + +..., где "-" означает неделимость. Таких групп от 1 до 100 будет 33, в каждой группе будет по 2 делящихся числа. Таким образом ответ - 66.

Для собеседования хватит и эвристики, но избавиться от неё можно с помощью метода математической индукции.

Далее докажем, что числа в последовательности с порядковым номером, кратным трём, делятся на 3.
первое такое число - 123 делится на 3, поскольку сумма его цифр равна 6. Пусть член последовательность под номером k (кратным трём) делится на 3. Тогда член последовательности под номером k+3 также будет делиться, поскольку к сумме цифр k-го члена прибавятся числа k+1, k+2 и k+3. Их сумма равна 3*k + 6, то есть делится на 3. Значит сумма цифр члена под номером k+3 также делится на 3.

Аналогично доказывается делимость членов с номером 3*t-1 и неделимость на 3 членов с номером 3*t-2.

Доказав обнаруженную последовательность чередования делимости/неделимости, также находим ответ - 66.