Хорошая задачка
Oct. 11th, 2019 05:22 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkvia
Мне повезло: у меня случился инсайт, и процесс решения занял секунд 10.
Комменты открыты.
An auditorium with 200 seats, numbered from 1 to 200, is filled to capacity. A speaker, who happens to be a mathematician, steps up to the podium overlooking the audience and pauses for a moment. “You know,” she says, “I’m thinking of a rather large whole number. Every seat number in this auditorium evenly divides my number, except for two of them — and those two seats happen to be next to each other.”
As you’d expect, adjacent seats in the auditorium have consecutive numbers. Which two numbers was the speaker referring to?
Комменты открыты.
no subject
Date: 2019-10-12 12:41 am (UTC)no subject
Date: 2019-10-12 01:11 am (UTC)no subject
Date: 2019-10-12 01:13 am (UTC)no subject
Date: 2019-10-12 05:19 am (UTC)no subject
Date: 2019-10-12 12:56 am (UTC)То есть, 127 (простое) и 128 (степень). Может и еще какие-то есть.
Это я со второй попытки догадался.
no subject
Date: 2019-10-12 01:13 am (UTC)no subject
Date: 2019-10-12 02:46 am (UTC)no subject
Date: 2019-10-12 01:05 am (UTC)no subject
Date: 2019-10-12 01:12 am (UTC)факториал
Date: 2019-10-12 04:04 am (UTC)Re: факториал
Date: 2019-10-12 04:33 am (UTC)no subject
Date: 2019-10-12 07:14 am (UTC)Perhaps, 127 (prime to the power 1) and 128 (prime to the power 7) are the two consecutive seats.
no subject
Date: 2019-10-12 07:19 am (UTC)no subject
Date: 2019-10-12 07:44 am (UTC)no subject
Date: 2019-10-12 08:50 am (UTC)no subject
Date: 2019-10-12 09:15 am (UTC)p^i * q^j * ... (a product of some primes to some powers)
It is not possible for the solution to have a number with all powers being zero, because that is 1, and any number is a multiple of 1. So all solutions must have some non-zero powers.
It is not possible for the solution to have a number that has more than one prime in its factorisation, which can be seen as follows.
If the number is a multiple of all other numbers except some chosen p^i * q^j for non-zero i and j, then of course it is a multiple of p^i and q^j, and, p^i and q^j being co-prime, it also is a multiple of p^i * q^j.
So the solution can only consist of numbers like p^i for some prime p and non-zero i.
Since the seat numbers are adjacent, one of them is even. Given the conclusions above, it also means it must be not just an even number, but necessarily a power of 2.
If the number were divisible by the biggest power of 2 that is less than 200, it is also divisible by any smaller power of 2. So we have to pick one seat with the biggest power of 2 that is less than 200, which is 128.
The other seat must necessarily be a power of a single prime, too. So we check 127 and 129. 129 is not a prime, 127 is, so we have a unique solution.
no subject
Date: 2019-10-12 08:40 am (UTC)Ни одно из искомых чисел не может раскладываться в произведение двух взаимнопростых. Значит каждое из них есть степень простого. Одно из них чётное, следовательно, оно будет степенью двойки. Это число не может быть меньшим 128-ми, ибо иначе 128 также не делило бы загаданное число, что противоречит условиям наложенным на загаданное число. Значит чётное число в искомой паре 128. Так как 129 составное, оно не подходит в качестве второго числа пары. Остаётся 127, которое простое. Легко видеть, что наименьшее общее кратное чисел от 1 до 200, исключая 127 и 128, не будет делиться ни на 127, ни на 128, но будет кратным всем остальным числам от 1 до 200.
no subject
Date: 2019-10-12 03:21 pm (UTC)no subject
Date: 2019-10-12 07:01 pm (UTC)