Паритет – 3 – Останній номер, що залишився
Числа від 1 до 5 записані на дошці. Потім вибираються пари чисел, стираються та замінюються їхньою різницею. Це продовжується, доки не залишиться одне число. У наведеному нижче прикладі це число 1.
1 2 3 4 5 => 1 2 4 2
1 2 4 2 => 2 2 3
2 2 3 => 2 1
2 1 => 1
ВИКЛИК
Наскільки малим може бути це одне число? Чи може воно бути 0? Чи зміниться ваша відповідь, якщо числа зміняться від 1 до 6 або від 1 до 7?
1 2 3 4 5 => ?
ПОЯСНЕННЯ
Для заданого списку чисел, наприклад, від 1 до 5, які останні числа можливі? Що таке
найменше та найбільше можливе останнє число? Коли у списку можливих чисел може з'явитися 0 або верхнє число?
примітки
ВИКЛИК
Це дуже схоже на головоломку, яка запитує, які числа можливі, якщо ми беремо числа від 1 до 5 і ставимо знаки додавання або віднімання між кожною парою чисел – наприклад, 1 + 2 + 3 – 4 + 5 або 1 + 2 – 3 + 4 + 5. Перевага використання цієї форми головоломки полягає в тому, що не буде задіяно від’ємних чисел.
Кілька простих зауважень для початку. Усі різниці невід'ємні, тому кінцева відповідь ніколи не може бути меншою за 0. Числа, які створюються з різниць, отримують або з вихідних чисел, або з чисел, похідних від цих чисел. Отже, максимальне число, яке можна використовувати з різницею, це найбільше число, яке дорівнює 5. Ми хочемо знати, які з чисел від 0 до 5 є можливими кінцевими відповідями.
Розглянемо це як задачу на парні та непарні числа. Почнемо з підрахунку кількості непарних чисел. У випадку переходу від 1 до 5 це число дорівнює 3, що саме по собі є непарним числом. Отже, у нас є непарна кількість непарних чисел. Складіть список того, що відбувається, коли ви берете різницю: 1) Якщо обидва числа парні, результат є парним числом, і загальна кількість непарних чисел не змінюється; 2) якщо одне число непарне, а інше парне, результат є непарним числом, і загальна кількість непарних чисел не змінюється; та 3) якщо обидва числа непарні, то результат є парним числом, і загальна кількість непарних чисел зменшується на два. У всіх випадках загальна кількість непарних чисел або залишається незмінною, або зменшується на два.
Результат: Якщо ми почнемо з непарної кількості непарних чисел, то закінчимо з непарною кількістю (1). Якщо ми почнемо з парної кількості непарних чисел, то закінчимо з парною кількістю (0).
У випадку переходу від 1 до 5 ми почали з непарної кількості непарних чисел, тому кінцева відповідь має бути непарною. Кінцева відповідь має бути 1, 3 або 5. Деякі швидкі експерименти показують, що всі вони можливі.
Аналіз абсолютно такий самий для чисел від 1 до 6, оскільки все ще є три непарні числа.
Для діапазону від 1 до 7 тепер є парна кількість непарних чисел, тому в кінці буде нуль непарних чисел, а можливі останні числа - 0, 2, 4 або 6 (які можуть зустрічатися всі).
ПОЯСНЕННЯ
Легко побачити, коли можливе отримання 0. Почніть з об'єднання послідовних чисел зверху та знаходження їхніх різниць. Це дає набір одиниць. Якщо є парна кількість одиниць, то ви можете отримати 0, а якщо є непарне число, то ви можете отримати 1. Не дивно, що це те саме, що з'ясувати, з якої кількості непарних чисел ви почали. Візьмемо, наприклад, числа від 1 до 7: (7 6) (5 4) (3 2) 1 => 1 1 1 1 => (1 1) (1 1) => 0 0 => 0.
Ви можете зробити те саме, щоб перевірити, чи можливе верхнє число. З'єднайте послідовні числа, починаючи зверху, пропускаючи верхнє число. Порахуйте різниці цих пар. Тепер у вас є список одиниць разом із верхнім числом. Скоротіть список одиниць до одного 0 або однієї одиниці. Порахуйте різницю цього числа разом із верхнім числом!