І? Задача не про те, щоби порахувати, як це робити для довільної різної ваги, а доказати, що, яка б не була вага цих каменів, менше, ніж за (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 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)