НГУ

Форумы НГУ
Текущее время: Чт фев 22, 2018 11:43 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Два мудреца
СообщениеДобавлено: Вт фев 22, 2005 1:22 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт фев 22, 2005 12:20 pm
Сообщения: 16
Чувствую здесь есть люди, которые могут расколоть задачку, над которой сам вечерок просидел. Возможно и решение будет лучше моего.

Некто сказал мудрецам A и B:
- Я задумал два натуральных числа. Каждое из них больше единицы, а сумма их меньше ста. Мудрецу А я сейчас сообщу по секрету от В произведение этих чисел, а мудрецу В по секрету от А - их сумму. Он выполнил обещанное и предложил отгадать задуманные числа.
Между А и В произошел следующий диалог:
А: - Я не могу определить числа.
В: - А я знал, что ты не сможешь.
А: - Тогда я знаю эти числа.
В: - Теперь и я знаю.

Определите задуманные числа.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср фев 23, 2005 12:17 pm 
Не в сети
Начинающий автор

Зарегистрирован: Чт май 27, 2004 9:35 pm
Сообщения: 212
Откуда: А. Карташов
4,13


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 3:17 am 
Не в сети
Опытный автор

Зарегистрирован: Пн сен 13, 2004 12:08 am
Сообщения: 406
Нда-а-а... Теоретически, задача действительно решабельная. Но практически, не вижу способа решить ее быстрее, чем за вечер.

_________________
КТО ИЩЕТ СМЫСЛ - ТОТ ГЛЯДИТ НА НЕБЕСА...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 1:58 pm 
Не в сети
Начинающий автор

Зарегистрирован: Чт май 27, 2004 9:35 pm
Сообщения: 212
Откуда: А. Карташов
решается перебором. Где-то около часа, а если делать по порядку - то минут 20ть.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 9:01 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн сен 13, 2004 12:08 am
Сообщения: 406
Andr писал(а):
решается перебором. Где-то около часа, а если делать по порядку - то минут 20.
Ничего подобного. Можно еще согласиться, что за 20 минут пара {4,13} может быть найдена как ВОЗМОЖНОЕ решение. Но условие задачи подразумевает доказательство того, что ДРУГИХ решений НЕТ. Тут на перебор уже и часа близко не хватит.

_________________
КТО ИЩЕТ СМЫСЛ - ТОТ ГЛЯДИТ НА НЕБЕСА...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 9:24 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Программу можно минут за двадцать написать. А уж работать она будет явно меньше секунды.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 9:25 pm 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
Пару лет назад на Турнире Городов была похожая задача.

Задача. Саша и Маша загадали по натуральному числу и сказали их Васе. Вася написал на одном листе бумаги сумму загаданных чисел, а на другом --- их произведение, после чего один из листов спрятал, а другой (на нем оказалось написано число 2002) показал Саше и Маше. Увидев это число, Саша сказал, что не знает, какое число загадала Маша. Услышав это, Маша сказала, что не знает, какое число загадал Саша. Какое число загадала Маша?

P.S. В этой задаче никакого перебора не надо, всё просто решается.

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 9:27 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн сен 13, 2004 12:08 am
Сообщения: 406
Andr писал(а):
решается перебором. Где-то около часа, а если делать по порядку - то минут 20ть.
Коба писал(а):
Программу можно минут за двадцать написать. А уж работать она будет явно меньше секунды.
Аргументы - в студию, пожалуйста!

_________________
КТО ИЩЕТ СМЫСЛ - ТОТ ГЛЯДИТ НА НЕБЕСА...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 9:30 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
SMS писал(а):
Аргументы - в студию, пожалуйста!


Текст программы, что ли? Если да, могу написать и выложить. У меня ее пока нет, я задачку не решал.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 9:34 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн сен 13, 2004 12:08 am
Сообщения: 406
Михаил Макаров писал(а):
Пару лет назад на Турнире Городов была похожая задача.

Задача. Саша и Маша загадали по натуральному числу и сказали их Васе. Вася написал на одном листе бумаги сумму загаданных чисел, а на другом --- их произведение, после чего один из листов спрятал, а другой (на нем оказалось написано число 2002) показал Саше и Маше. Увидев это число, Саша сказал, что не знает, какое число загадала Маша. Услышав это, Маша сказала, что не знает, какое число загадал Саша. Какое число загадала Маша?

P.S. В этой задаче никакого перебора не надо, всё просто решается.
Дык ясен перец! В Вашей задаче сумма указана явно. А в задаче diggera только чтобы, например, найти все произведения, при которых B имеет право сказать "Я знал, что ты не сможешь", требуется ай-ай-ай как поработать...

_________________
КТО ИЩЕТ СМЫСЛ - ТОТ ГЛЯДИТ НА НЕБЕСА...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 9:41 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн сен 13, 2004 12:08 am
Сообщения: 406
Коба писал(а):
SMS писал(а):
Аргументы - в студию, пожалуйста!
Текст программы, что ли? Если да, могу написать и выложить. У меня ее пока нет, я задачку не решал.
Да черт с ним, с текстом, алгоритм хотя-бы кто-нибудь выложил, как он типа собирается решать эту задачу за двадцать минут... :-? Или тут одни асы олимпиадных боев собрались?...

_________________
КТО ИЩЕТ СМЫСЛ - ТОТ ГЛЯДИТ НА НЕБЕСА...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 9:46 pm 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
SMS писал(а):
Дык ясен перец! В Вашей задаче сумма указана явно.

Really? Там вообще-то не сказано, что 2002 --- это сумма. Это число на одной из бумажек, неизвестно на какой.

P.S. И ещё, это задача не моя. У неё есть вполне конкретный автор: Д. Кириенко.

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 10:04 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
SMS писал(а):
Да черт с ним, с текстом, алгоритм хотя-бы кто-нибудь выложил...


Искомая пара чисел (n,m), где 1 < n <= m должна обладать следующими свойствами.

1) n+m < 100
2) Оба числа n и m не могут быть простыми.
3) Сумма n+m не является суммой двух простых чисел.
4) Для любой пары чисел 1 < k <= l, такой что k+l < 100 и k*l = n*m либо (k,l) = (n,m), либо k+l является суммой двух простых.
5) Для любой пары 1 < k <= l, такой что k+l = n+m либо (k,l) = (n,m), либо (k,l) не удовлетворяет условиям 2-4 (сформулированным для (n,m)).

Перебираем все пары. Та из них, которая удовлетворяет условиям 1-5, является ответом.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 24, 2005 10:36 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн сен 13, 2004 12:08 am
Сообщения: 406
Коба писал(а):
Искомая пара чисел (n,m), где 1 < n <= m должна обладать следующими свойствами.

1) n+m < 100
2) Оба числа n и m не могут быть простыми.
3) Сумма n+m не является суммой двух простых чисел.
4) Для любой пары чисел 1 < k <= l, такой что k+l < 100 и k*l = n*m либо (k,l) = (n,m), либо k+l является суммой двух простых.
5) Для любой пары 1 < k <= l, такой что k+l = n+m либо (k,l) = (n,m), либо (k,l) не удовлетворяет условиям 2-4 (сформулированным для (n,m)).

Перебираем все пары. Та из них, которая удовлетворяет условиям 1-5, является ответом.
Вот именно, что проверить 1)-4) на руках еще реально, а вот париться над 5) я даже не стал... Кстати, поправка: в 1) должно быть также 5 < n+m.

В общем, я хотел озвучить в точности следующее. Во-первых, если человек в своей жизни не сталкивался с подобными задачами вообще, то родить четкую формулировку условий 1)-5) за 20 минут нереально. Во-вторых, я не вижу способа устроить рациональный перебор для проверки 1)-5), чтобы уложиться, скажем в пару часов спокойной работы. Тем более, что после того как сами 1)-5) получены, желание вообще делать этот перебор (особенно после нахождения пары {4,13}) равно минус бесконечности.

_________________
КТО ИЩЕТ СМЫСЛ - ТОТ ГЛЯДИТ НА НЕБЕСА...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт фев 25, 2005 12:17 am 
Не в сети
Начинающий автор

Зарегистрирован: Чт май 27, 2004 9:35 pm
Сообщения: 212
Откуда: А. Карташов
SMS писал(а):
Andr писал(а):
решается перебором. Где-то около часа, а если делать по порядку - то минут 20.
Ничего подобного. Можно еще согласиться, что за 20 минут пара {4,13} может быть найдена как ВОЗМОЖНОЕ решение. Но условие задачи подразумевает доказательство того, что ДРУГИХ решений НЕТ. Тут на перебор уже и часа близко не хватит.


После того, как было найдено возможное решение (где-то около часа) на перебор оставшихся у меня ушло около 15 минут.

Собственно, вот решение:

1) Сумма от 4 до 99. Выбрасываем все числа, которые могут оказаться суммой двух простых, или одного простого больше 50 и 4 или 6:

Остаются возможные суммы: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53 - всего 11 вариантов.

2) Разберём вариант суммы 11. 11=2+9=3+8=...

2*9=6*3. 6+3=9 - эта сумма не входит в наши 11 вариантов, следовательно, поэтому после фразы "я знал, что ты не можешь догадаться", мудрец А определяет цифры.

3*8=6*4. 6+4=10 - опять не входит, опять мудрец А может догадаться.

Поскольку здесь два возможных варианта, то мудрец Б не может узнать точно, какой из них, следовательно 11 тоже выбрасываем.

3) Перебираем 17=2+15=3+14=4+13=5+12=6+11=7+10=8+9. Находим только одну такую пару - 4, 13 - возможное решение.

4) Остальные быстро отбрасываем по тому же принцмпу, что и 11:
23 - пары 4,19 и 7,16
27 - 2.25 4.23
29 - 2.27 4.25
35 - 3.32 4.31
37 - 5.32 16.31
41 - 9.32 25.16
47 15.32 16.31
51 19.32 35.16
53 21.32 37.16

Поиск нужных пар был облегчен тем, что я старался брать такие, чтобы одно из чисел было степенью 2х, а другое - простым или простым в квадрате. Почему, объяснять не буду :).

Больше всего времени ушло на нахождение способа, решения, перебор занял меньше времени.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 17


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB