Загадки @ smeha.net — Математичні

14.08.2015

Загадки @ smeha.net — Математичні

Є 2N пронумерованих монет, причому: усі справжні монети важать однаково, всі фальшиві також важать однаково, фальшива монета легше справжньою. монети з номерами від 1 до N справжні, а монети з номерами від N+1 до 2N — фальшиві. З цих двох тверджень суддя знає тільки перше, а експерт — обидва.

Як експерту за три зважування на чашкових вагах без гир переконати суддю в справедливості другого твердження?

b: N=9

Завдання «a» пропонувалася на одній із Всесоюзних мат. олімпіад у 1970-х роках. З тих пір число N=7 (і в загальному випадку, N=2^K-1 K зважувань) вважалося не улучшаемым. І тим не менш, це не так. Поліпшення завдання («b») придумано С. Токарєвим в 1997 році.

a) 1) Експерт зважує монети 1 і 8. (1 > 8)

Суддя переконується, що 8 — фальшива.

2) Експерт зважує 1+8 і 9+10. (1+8 > 9+10)

Суддя переконується, що 9+10 легше, ніж одна фальшива і одна справжня. Отже, він робить висновок, що і 9, і 10 — фальшиві.

3) Експерт зважує 1+8+9+10 і 11+12+13+14.

Аналогічно, суддя може зробити висновок про всіх монетах 11-14. Зауважимо, що справжня монета потрібна рівно одна.

b) Попереднє дію: експерт групує монети в такі три купки: А(1, 2; 10, 11); Б(3, 4, 5; 12, 13, 14); В(6, 7, 8, 9; 15, 16, 17, 18); У кожній купці порівну справжніх і фальшивих монет, експерту це відомо, а судді буде доведено в результаті зважувань.

1) На ліву чашку ваг кладуть справжні монети з купки А й фальшиві з купки Б, а на праву — фальшиві з купки А й справжні з купки Б. Права чашка важче лівої.

2) На ліву чашку ваг кладуть справжні монети з купки Б і фальшиві з купки, а на праву — фальшиві з купки Б і справжні з купки Ст. Права чашка важче лівої.

3) На ліву чашку ваг кладуть справжні монети з купки і фальшиві з купок А і Б, а на праву — фальшиві із купки В і справжні з купок А і Б. Права чашка важче лівої.

Позначимо x різницю ваг справжніх і фальшивих монет купки A, т. е.(1+2) -(10+11), y — то ж для купки Б, тобто(3+4+5)-(12+13+14), z- (6+7+8+9)-(15+16+17+18).

Наші зважування довели судді наступні три нерівності:

y > x; z > y; x+y > z.

Оскільки x,y,z — цілі числа, то строгі нерівності можна замінити на несуворі:

y >= x+1

z >= y+1

x+y >= z+1.

Звідси: x+y >= y+2 => x >= 2;

x+y >= x+3 => y >= 3;

2z >= x+y+3 >= z+4 => z >= 4.

Короткий опис статті: загадки з цифрами

Джерело:

Загадки @ smeha.net — Математичні

Також ви можете прочитати