Назовите несколько (два или три) значений переменной а, при которых значение выражения: а) кратно 2; б) кратно 3; в) кратно 4; г) кратно 5; д) кратно 7; е) кратно 9; ж) кратно 10; з) кратно 12; и) кратно 14; к) кратно 15.

1) Взаимно простые числа - такие, что не имеют общих делителей, кроме 1. Для них НОК - просто произведение:

3, 4: НОК(3, 4) = 12

3, 7: НОК(3, 7) = 21

3, 8: НОК(3, 8) = 24

4, 7: НОК(4, 7) = 28

4, 9: НОК(4, 9) = 36

6, 7: НОК(6, 7) = 42

7, 8: НОК(7, 8) = 56

7, 9: НОК(7, 9) = 63

8, 9: НОК(8, 9) = 72

2) Эти числа должны иметь вид x, n*x. Максимальное число, на которое делится каждое из них, равно x, а минимальное число, которое делится на каждое из них равно n*x.

3, 6: НОД(3, 6) = 3; НОК(3, 6) = 6

3, 9: НОД(3, 9) = 3; НОК(3, 9) = 9

4, 8: НОД(4, 8) = 4; НОК(4, 8) = 8

3) Сюда подойдут все пары, выписанные в пункте 2. Остальные пары:

4, 6: НОД(4, 6) = 2; НОК(4, 6) = 12

6, 8: НОД(6, 8) = 2; НОК(6, 8) = 24

6, 9: НОД(6, 9) = 3; НОК(6, 9) = 18

Пример вычисления для НОД и НОК пары 6 и 9:

Раскладываем на простые множители: 6 = 2 * 3, 9 = 3 * 3

НОД - произведение всех простых множителей, входящих одновременно в оба разложения. НОД(6, 9) = 3

НОК - произведение всех простых множителей, входящих хотя бы в одно разложение. НОК(6, 9) = 2 * 3 * 3 = 18.

Для упрощения жизни можно заметить, что для пары чисел x и y верно равенство: НОД(x, y) * НОК(x, y) = xy. Тогда, например, вычислив, что НОД(6, 9) = 3, сразу находим, что НОК(6, 9) = 6 * 9 / НОД(6, 9) = 54 / 3 = 18

Поскольку весы именно чашечные, то задача нахождения фальшивой монеты из N сводится к бинарному поиску - мы каждый раз делим исходную кучку пополам (или на три части, если пополам не делится), определяем ту, которая легче, затем поступаем с ней аналогично. И т.д. пока сравнение не сведется к 2-м монетам - более легкая из них и есть искомая. При этом для N монет нам понадобится log2(N) взвешиваний. Если N не степень двойки, то округление идет до ближайшей СЛЕДУЮЩЕЙ. Т.о. в нашем примере log2(N) = 4. Откуда N = 2^4 = 16. 16 монет.