Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Статья: Много битов из ничего

Название: Много битов из ничего
Раздел: Рефераты по математике
Тип: статья Добавлен 03:59:08 24 марта 2008 Похожие работы
Просмотров: 41 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

С. Артёмов, Ю. Гиматов, В. Фёдоров

Он думал, что уснула я

И всё во сне стерплю.

Иль думал, что я думала,

Что думал он «я сплю».

С. Маршак. Из Ковентри Патмора.

Предлагаем вниманию читателей задачу, требующую для решения весьма изощрённой логики:

Математик R сказал математикам P и S: «Я задумал два натуральных числа. Каждое из них больше единицы, а сумма их меньше ста. Математику P я сейчас сообщу – по секрету от S – произведение этих чисел, а математику S я сообщу – по секрету от P – их сумму». Он выполнил обещанное и предложил отгадать задуманные числа. Между P и S произошёл следующий диалог (высказывания P мы обозначаем буквой π с индексами, высказывания S – буквой σ):

– Я, пожалуй, не могу сказать, чему равны задуманные числа. (π1)
– Я заранее знал, что Вы этого не сможете. (σ1)
– А ведь тогда я их знаю. (π2)
– А тогда и я их знаю. (σ2)

Попробуйте теперь и вы отгадать задуманные числа.

1. Неужели их можно отгадать?

При первом взгляде на задачу она представляется неразрешимой: как можно отгадать числа, когда про них ничего не сказано?

Попробуем на примере. Пусть R задумал 7 и 42. Тогда он сообщил P число 294, S – 49. Ну, а что дальше? Р сказал, что он не может отгадать задуманные числа. Ну, конечно же не может – он знает только их произведение. Хотя, впрочем, он знает ещё, что они натуральные, больше единицы и их сумма меньше ста. А что это даёт?

Обозначим задуманные числа через k0 и l0, причём пусть для определённости k0 ≤ l0. Обозначим ещё произведение k0·l0 через p0, сумму k0 + l0 через s0.

Итак, P сообщили, что p0 = 294.

Тогда k0 может равняться 2, 3, 6, 7 и 14, а l0 будет при этом равно, соответственно, 147, 98, 49, 42 и 21. Первые два значения для k0 нам не подходят – при них s0 > 100. Всё равно остаются ещё три возможности. Значит, P действительно не может отгадать задуманные числа.

Идём дальше. S утверждает, что он заранее знал, что P не сможет отгадать k0 и l0. Как S пришёл к такому выводу? Наверняка он попробовал всеми возможными способами представить известное ему s0 в виде суммы двух допустимых слагаемых:

49 = 2 + 47 = 3 + 46 = ... = 24 + 25.

R мог задумать любую из этих пар чисел. Он сообщил P какое-то из произведений i·(49 – i), и S утверждает, что ни по одному из них P не может отгадать задуманные числа.

А если при некотором i оба числа i, 49–i – простые? Например, если R задумал 2 и 47, то P он сообщил 94, и P прекрасно может отгадать задуманные числа.

Следовательно, если R задумал 7 и 42, то S, получив s0 = 49, не имел бы права произнести (σ1). Значит, R не мог задумать 7 и 42.

Таким образом, кое-что о задуманных числах сказать всё-таки можно.

Преодолев первоначальные сомнения, подумаем, в каком направлении двигаться. Один способ отгадывания уже виден: брать всевозможные пары чисел k0, l0, удовлетворяющие неравенствам

2 ≤ k0 ≤ l0 ≤ 97, (1)
2 ≤ k0 + l0 ≤ 99, (2)

и проверять, «выдерживают» ли они диалог (π1) – (σ2).

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

Прежде всего давайте сначала искать не k0 и l0, а их сумму s0: для пары (k0, l0) возможных вариантов больше двух тысяч, а для s0 – меньше ста. Впрочем, и на этом пути лобовой перебор длинен и скучен.

2. Около гипотезы Гольдбаха-Эйлера

Какую информацию можно извлечь из (π1) и (σ1)? Что они означают?

(π1),

очевидно, означает, что

p0 не однозначно разлагается в произведение двух множителей, удовлетворяющих неравенствам (1), (2);

(π′1)
(σ1)

означает, что

При любом разложении числа s0 сумму двух слагаемых, удовлетворяющих неравенствам (1), их произведение обладает свойством (π′1).

(σ′1)

Высказывание (π′1) позволяет отбросить некоторые произведения, (σ′1) – некоторые суммы.

Из (σ′1) вытекает, что s0 не представимо в виде суммы двух простых чисел: если s0 = q1 + q2, где q1, q2 – простые, то число q1·q2 единственным образом разлагается в произведение двух множителей, удовлетворяющих неравенствам (1), (2), и, следовательно, не обладает свойством (π′1).

Но любое чётное число, удовлетворяющее неравенствам (2), представимо в виде суммы двух простых (это доказывается последовательной проверкой чисел 4, 6, 8, .... 98).

Следовательно, s0 – нечётное. Кроме того, s0–2 – составное: иначе s0 = 2 + (s0 – 2) представлялось бы в виде суммы двух простых. После отбрасывания чисел, не удовлетворяющих этим двум условиям, для s0 остаётся 24 возможности.

Выше мы воспользовались тем, что все чётные числа от 4 до 98 представимы в виде суммы двух простых.

В 1742 г. член Петербургской Академии наук Христиан Гольдбах в письме к Леонарду Эйлеру высказал предположение, что любое нечётное число, большее пяти, может быть представлено в виде суммы трёх простых чисел. В ответном письме Эйлер выдвинул гипотезу, что каждое чётное число, большее двух, представимо в виде суммы двух простых чисел. (Из гипотезы Эйлера гипотезу Гольдбаха вывести очень легко – сделайте это!)

В течение почти двухсот лет гипотезы Гольдбаха и Эйлера казались совершенно недоступными для доказательства, хотя непосредственным перебором математик Миле проверил их до 9 000 000.

В 1930 г. замечательный советский математик Л. Г. Шнирельман доказал существование такого k, что каждое натуральное число n > 1 может быть представлено в виде суммы не более k простых чисел. Число k у Шнирельмана было довольно велико. В настоящее время доказано, что теорема Шнирельмана верна при k = 20.

В 1934 г. академик И. М. Виноградов доказал существование такого n0, что любое нечётное число n > n0 представимо в виде суммы трёх простых чисел. Казалось бы, в век ЭВМ можно было бы поручить машине проверить «остальные» числа (от 7 до n0), но «постоянная Виноградова» n0 так велика (по последним оценкам n0 > 265536), что эта проверка превосходит возможности современных ЭВМ.

В доказательстве же гипотезы Эйлера до сих пор не достигнуто никакого существенного успеха.

3. Дальше в лес

Оказывается, из (σ′1) можно вывести, что

s0 < 55. (3)

В самом деле, предположим, что s0 ≥ 55. Тогда s0 не обладает свойством (σ′1): можно так разложить его в сумму двух слагаемых, удовлетворяющих неравенствам (1), что для их произведения не будет выполнено условие (π′1). Это разложение: s0 = (s0 – 53) + 53. Из s0 ≥ 55 вытекает s0 – 53 ≥ 2. Произведение (s0–53)·53 единственным образом разлагается на два множителя, сумма которых меньше ста: поскольку 53 – простое число, один из множителей обязательно имеет вид 53d; так как 53·2 > 100, d = 1. Но по условию s0 обладает свойством (σ′1). Противоречие!

После (3) для s0 остается уже 11 возможностей:

11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53. (4)

Попробуем теперь без перебора установить, какие из чисел (4) удовлетворяют условию (σ′1). Пусть s – произвольное из чисел (4). Поскольку s нечётно, всякое его разложение в сумму имеет вид s = 2а + m. Допустим, s не обладает свойством (σ′1). Тогда найдётся такое а, что произведение 2a·m «расшифровывается» однозначно.

Это a не может равняться единице, так как в этом случае s = 2 + m, а произведение 2m двояко разлагается в произведение. В самом деле, поскольку m = s–2 – составное нечётное число, m = pq, где р > 2 и q > 2. Оба разложения

2m = 2·pq = 2p·q

годятся: 2 + pq = 2 + m = s < 100 и 2p + q = 2 + pq – (p – 1)(q – 2) < 2 + pq < 100.

Значит, a ≥ 2.

Если a ≠ m, то 2a·m и 2m·a – два различных разложения. Поскольку 2a + m = s < 100 и s не обладает свойством (σ′1), должно быть 2m + a ≥ 100. Так как s = 2a + m ≤ 53, имеем m ≤ 53 – 2a, 2m + a ≤ 106 – 3a. Из 2m + a ≥ 100 и 2m + a ≤ 106 – 3a вытекает a ≤ 2. Следовательно, a = 2. Из 2m + a ≥ 100 и m ≤ 53 – 2a получаем теперь m = 49. Итак, в этом случае s = 53, причём «подозрительным» является разложение 53 = 4 + 49.

Если же a = m, то s = 3a делится на 3. В (4) таких чисел два: 27 и 51. «Подозрительными» являются разложения 27 = 9 + 18 и 51 = 17 + 34.

Число 51 действительно не обладает свойством (σ′1): 51 = 17 + 34, и произведение 17·34 при разложении на два множителя даёт только одну сумму, меньшую ста. Таким образом, его можно выбросить из списка «кандидатов в s0».

Числа 27 и 53 удовлетворяют условию (σ′1): 9·18 = 2·81 и 2 + 81 < 100; 4·49 = 7·28 и 7 + 28 < 100.

Итак, для дальнейшего исследования осталось 10 кандидатов: 11, 17, 23, 27, 29, 35, 37, 41, 47, 53, причём все они обладают свойством (σ′1).

4. «Тогда и я их знаю»

Используем, наконец, (π2) и (σ2).

Можно было бы истолковать (π2) и (σ2) подобно тому, как мы это сделали с (π1) и (σ1). Мы попробуем обойтись без этого.

Из (σ2) и (3) можно вывести

s0 < 33. (5)

Допустим противное: s0 ≥ 33. Тогда математик S, разлагая всеми возможными способами s0 в сумму двух слагаемых, имел бы среди этих разложений s0 = (s0 – 31) + 31 = (s0 – 29) + 29.

Если бы P было сообщено произведение (s0–31)·31, то он мог бы, сообразив (3) и учтя, что 31 – простое число, понять, что (s0–31)·31 единственным образом разлагается в произведение двух множителей, сумма которых удовлетворяет (3). В этом случае P отгадал бы k0 и l0.

Аналогичная возможность была у P, если ему было сообщено произведение (s0–29)·29,.

Значит, в случае s0 ≥ 33, S и после (π2) не смог бы точно назвать k0, l0, т.е. не смог бы произнести (σ2).

После (5) остается 5 кандидатов: 11, 17, 23, 27, 29.

Если p0 имеет вид 2n·p, где p – нечётное простое число, то P однозначно определяет k0 и l0, потому что из всех сумм 2n–t + 2tp нечётна только одна: 2n + p. Поэтому, если s0 двумя способами представимо в виде 2n + p, то S опять-таки не может произнести (σ2).

Это соображение позволяет отсеять ещё 3 кандидата: 11 = 4 + 7 = 8 + 3, 23 и 27.

Остались 2 кандидата: 17 и 29.

5. Тогда и мы их знаем

29 тоже не годится, поскольку 29 = 4 + 25 = 16 + 13: если бы P имел p0 = 16·13, он бы отгадал k0 и l0, так как среди сумм 24–t + 2t·13 нечётна только одна; если бы P имел p0 = 4·25, он бы тоже отгадал k0 и l0: среди соответствующих сумм нечётна, кроме 29, ещё только 25 (4·25 = 5·20), но 25–2 – простое число.

Итак, либо s0 = 17, либо задача не имеет решений.

Какое же p0 могло быть у P при s0 = 17? Переберём все разложения числа 17 в сумму двух слагаемых:

17 = 2 + 15 = 3 + 14 = ... = 8 + 9.

При любом из произведений, кроме 4·13, P не смог бы произнести (π2). Например, если бы P имел p0 = 30, он среди разложений числа 30 в произведение двух множителей увидел бы и 30 = 2·15, и 30 = 5·6, но как 17, так и 11 обладают свойством (σ′1).

Остается единственный кандидат для p0: 52. Этот кандидат дает возможность P произнести (π2): среди всех разложений числа 52 в произведение двух множителей существует ровно одно: 52 = 4·13, дающее нечётную сумму.

Итак, s0 = 17, p0 = 52, k0 = 4, l0 = 13.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений06:45:14 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
16:08:49 24 ноября 2015

Работы, похожие на Статья: Много битов из ничего

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150269)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru