Відкрив другу книжку на випадковому місці, попалася задача 4.5.2: Є n каменів різної ваги. В суді (чому в суді? ок, нехай, в суді) експерт, знаючи наперед вагу кожного каменя, хоче переконати присяжних, що якийсь особливо цінний для даного експерта камінь -- найважчий з усіх. Треба доказати, що це неможливо зробити менше, ніж за (n-1) зважувань.
Помітьте, ніяких обмежень на вагу каменів тут нема, отже можливий навіть сценарій, коли коли таке робиться одним зважуванням! Чи тут як в старому анекдоті, де "ви - дачник, а лекція для колгоспників", перефразованому, що книжка для програмістів, а я -- фізик?
Якщо найважчий камінь важчий (або рівно такий самий), як решта (n−1) каменів, то вистачить одного зважування (ок, двох, якщо це не терези, а scales, але тоді в програмістській задачці була би відповідь n). Всякий раз, коли якийсь з каменів важить так само або більше, ніж k інших каменів, це зменшує максимальну кількість зважувань на k−1 разів. Задачка має смисл лише якщо прийняти (абсолютно неприродню для фізика) умову, що порівнювати камені можна лише парами.
По умові всі камені різної ваги. Про зважувати тільки парами не сказано. Але не має сенсу порівнювати пару каменів з другою парою, бо нічого не дізнаємося.
Ну? Якщо один камінь важить стільки само, скільки важать всі інші, то навіщо зважувати більше, ніж один раз? Скільки би тих всіх інших каменів не було.
І? Задача не про те, щоби порахувати, як це робити для довільної різної ваги, а доказати, що, яка б не була вага цих каменів, менше, ніж за (n-1) зважень нічого доказати не вийде. Тепер уявімо, що камінь номер 1 важить так само (або більше), як решта (n-1) каменів разом. Кладемо цей камінь на ліву сторону терезів, решту каменів -- на прави, показуємо, що наш перший камінь переважує, і -- вуаля! він найважчий!
Умова задачі каже, що експерт (a) наперед знає вагу каменів і (b) просить доказати, що менше, ніж за (n-1) зважувань неможливо нічого доказати присяжним. Ну ось, контрприклад -- можливо доказати за одне зважування. Неможливо лише в тому випадку, якщо не існує жодної трійки каменів (i,j,k) таких, що їхня вага (нехай, вага каменя позначається величиною W з відповідним індексом) задовільняє нерівність Wi+Wj≤Wk Але в умові задачі про таку нерівність нема нічого, відповідно, навіть одного контрприкладу достатньо
Я оце лише написав -- там не написано, що питають про загальний випадок, якби було написано "в общем случае невозможно" -- я би слова не сказав, але просто "неможливо" спростовується простим контрприкладом.
Ось формулювання: Эксперт хочет убедить суд, что данный камень самый тяжёлый среди 𝑛 камней, сделав менее 𝑛 − 1 взвешиваний. Докажите, что это невозможно. (Веса камней неизвестны суду, но известны эксперту.) Я, наче, не настільки забув російську -- про те, що це має працювати для будь-якого розподілу ваги каменів тут не написано.
Я веду до чого: ясно, що в якомусь формулюванні ця задача має сенс, але так, як її записали, цього сенсу нема. Правильний запис повинен мати лише * або зважувати можна лише попарно, камінь проти каменя; * або вищезгадана умова про те, що жоден камінь не може бути важчим за два або більше інших каменів; * або забрати умову, що експерт наперед знає вагу всіх каменів; * або поміняти умову з просто "неможливо" на "можна знайти набір каменів, для якого неможливо"
Кожен з чотирьох перелічених варіантів -- уже інша задача
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
vak
no subject
Date: 2025-01-11 00:49 (UTC)Є n каменів різної ваги. В суді (чому в суді? ок, нехай, в суді) експерт, знаючи наперед вагу кожного каменя, хоче переконати присяжних, що якийсь особливо цінний для даного експерта камінь -- найважчий з усіх. Треба доказати, що це неможливо зробити менше, ніж за (n-1) зважувань.
Помітьте, ніяких обмежень на вагу каменів тут нема, отже можливий навіть сценарій, коли коли таке робиться одним зважуванням! Чи тут як в старому анекдоті, де "ви - дачник, а лекція для колгоспників", перефразованому, що книжка для програмістів, а я -- фізик?
no subject
Date: 2025-01-11 01:25 (UTC)no subject
Date: 2025-01-11 03:54 (UTC)Задачка має смисл лише якщо прийняти (абсолютно неприродню для фізика) умову, що порівнювати камені можна лише парами.
no subject
Date: 2025-01-11 04:09 (UTC)no subject
Date: 2025-01-11 04:10 (UTC)no subject
Date: 2025-01-11 04:15 (UTC)no subject
Date: 2025-01-11 04:20 (UTC)Тепер уявімо, що камінь номер 1 важить так само (або більше), як решта (n-1) каменів разом. Кладемо цей камінь на ліву сторону терезів, решту каменів -- на прави, показуємо, що наш перший камінь переважує, і -- вуаля! він найважчий!
no subject
Date: 2025-01-11 04:39 (UTC)no subject
Date: 2025-01-11 04:49 (UTC)Ну ось, контрприклад -- можливо доказати за одне зважування.
Неможливо лише в тому випадку, якщо не існує жодної трійки каменів (i,j,k) таких, що їхня вага (нехай, вага каменя позначається величиною W з відповідним індексом) задовільняє нерівність
Wi+Wj≤Wk
Але в умові задачі про таку нерівність нема нічого, відповідно, навіть одного контрприкладу достатньо
no subject
Date: 2025-01-11 04:55 (UTC)no subject
Date: 2025-01-11 04:57 (UTC)Ось формулювання:
Эксперт хочет убедить суд, что данный камень самый тяжёлый среди 𝑛 камней, сделав менее 𝑛 − 1 взвешиваний. Докажите, что это невозможно. (Веса камней неизвестны суду, но известны эксперту.)
Я, наче, не настільки забув російську -- про те, що це має працювати для будь-якого розподілу ваги каменів тут не написано.
no subject
Date: 2025-01-11 05:07 (UTC)no subject
Date: 2025-01-11 05:09 (UTC)Різниця між фізиком і програмістом -- у тому, що він сприймає за дефолт :)
no subject
Date: 2025-01-11 04:55 (UTC)* або зважувати можна лише попарно, камінь проти каменя;
* або вищезгадана умова про те, що жоден камінь не може бути важчим за два або більше інших каменів;
* або забрати умову, що експерт наперед знає вагу всіх каменів;
* або поміняти умову з просто "неможливо" на "можна знайти набір каменів, для якого неможливо"
Кожен з чотирьох перелічених варіантів -- уже інша задача
no subject
Date: 2025-01-11 04:57 (UTC)