Есть идея! - [6]
Тренер составил таблицу розыгрыша турнира, снабдив ее следующими пояснениями.
Тренер. Пять — число нечетное, поэтому в первой круге один участник турнира свободен от игры. Еще один участник свободен от игры во втором круге. Таким образом, всего за турнир будет сыграно 4 партии.
На следующий год в спортивный клуб записалось 37 школьников. Тренер снова составил таблицу розыгрыша турнира, постаравшись свести до минимума число участников, которые переходят в следующий круг без игры. Сколько партий было сыграно за весь турнир на этот раз?
Как, вы еще не сосчитали? А ведь задача решается просто! В каждой партии проигравший выбывает, а поскольку дли того, чтобы определить победителя, следует исключить всех участников, кроме одного, то за весь турнир должно состояться 36 партий. Не правда ли, все очень просто?
Если вы пытались решить задачу о турнире по настольному теннису «в лоб», составляя различные варианты таблиц розыгрыша турнира с 37 участниками, то, должно быть, заметили, что независимо от способа составления таблицы число участников, переходящих в следующий круг без игры, всегда равно 4. В общем случае число участников, для которых в очередном круге не хватает партнера, есть функция от числа n всех участников турнира. Кате установить, сколько участников вынуждены будут перейти в следующий круг без игры?
При заданном n число участников, остающихся без партнера, можно определить следующим образом. Вычтем из n наименьшую степень числа 2, которая больше или равна n. Полученную разность запишем в двоичной системе. Число единиц в двоичной записи и будет равно числу участников турнира, вынужденных перейти в следующий круг без игры из-за нехватки партнера. В нашей задаче мы вычтем 37 из 64 (то есть из 2>6) и получим разность, равную 27. Десятичное число 27 в двоичной системе имеет вид 11011. Поскольку в его записи 4 единицы, то за весь турнир без игры в следующий круг перейдут 4 игрока. Обоснование этого алгоритма для определения числа участников, которым не хватает партнера, мы предоставляем читателю в качестве интересного упражнения.
Описанный в задаче тип турнира иногда называют «игрой на вылет». Он аналогичен алгоритму, который вычислители, работающие на современных ЭВМ, используют для нахождения наибольшего элемента в множестве из n элементов: наибольший элемент находят, сравнивая попарно элементы множества и отбрасывая при очередном сравнении тот из двух элементов, который не больше другого. Как мы уже знаем, чтобы найти наибольший элемент, достаточно произвести ровно n − 1 попарных сравнений. При автоматической сортировке сравнивать можно не только по 2, но и по 3, 4 и т. д. элемента.
Автоматическая сортировка играет важную роль в вычислительной математике и в информатике. Ей посвящено немало книг. Каждый из нас без труда назовет длинный перечень примеров применения автоматической сортировки. Подсчитано, что примерно четверть машинного времени в научных и в технических расчетах затрачивается на решение задач, связанных с сортировкой данных.
Стаканчики профессора Квиббла
Как-то раз продавец прохладительных напитков Барни предложил двум покупателям следующую задачку.
Барни. Перед вами 10 бумажных стаканчиков, расставленных в ряд. В первые 5 стаканчиков я наливаю кинки-колу, остальные 5 стаканчиков остаются пустыми. Можно ли переставить 4 стаканчика так, чтобы пустые и полные стаканчики чередовались?
Барни. Правильно! Стоит лишь переставить второй стаканчик с седьмым, а четвертый с девятым, как задача будет решена.
Разговор Барни с покупателями услышал проходивший мимо профессор Квиббл, большой любитель неожиданных решений, который счел необходимым вмешаться.
Проф. Квиббл. Переставлять 4 стаканчика совсем не обязательно. Я берусь решить задачу, переставив лишь 2 стаканчика. Как, по-вашему, это возможно?
Проф. Квиббл. Мое решение проще простого. Я беру второй стаканчик и переливаю его содержимое в седьмой, а содержимое четвертого стаканчика — в девятый.
Хотя предложенное профессором Квибблом шуточное решение основано на неоднозначном толковании слова «переставить» (означающего не только «поменять местами», как полагал Барни, но и «поставить по-другому», чем и воспользовался профессор Квиббл), исходная задача не столь тривиальна, как может показаться. Рассмотрим, например, аналогичную задачу для случая, когда из 200 стаканчиков, выстроенных в ряд, в первые 100 налита кинки-кола, а 100 остальных оставлены пустыми. Сколько пар стаканчиков следует поменять местами, чтобы пустые и полные стаканчики чередовались?
Поскольку следить за 200 стаканчиками довольно трудно, разберем сначала ту же задачу при меньших значениях n, где n — число полных (или пустых) стаканчиков, и попытаемся подметить общую закономерность. Стаканчики можно «моделировать» фишками двух цветов, игральными картами, выложенными на столе рубашкой либо вверх, либо вниз, монетами и тому подобными предметами, наделенными каким-нибудь «двузначным» признаком. При n = 1 для решения задачи не требуется переставлять ни одной пары стаканчиков. При
Книга известного американского популяризатора науки М. Гарднера содержит множество занимательных задач и головоломок из самых различных областей математики. Благодаря удачному подбору материла, необычной форме его подачи и тонкому юмору автора она не только доставит удовольствие любителям математики, желающим с пользой провести свой досуг, но и может быть полезной преподавателям математики школ и колледжей в их работе.
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
Книга Гарднера — это популярное изложение специальной и общей теории относительности, действительно рассчитанное на миллионы читателей.Увлекательно и доступно написанная, она будет понятна всем, начиная со школьников старших классов. Особо следует отметить прекрасные иллюстрации. Благодаря им книга похожа на альбом под названием «Теория относительности в картинках».Впрочем, именно такой и должна быть популярная книга.
Имя Мартина Гарднера (р. 1914) хорошо известно в России. За свою долгую жизнь он написал более 70 книг, ставших популярными во всем мире, многие из них издавались и на русском языке. Гарднер — автор огромного количества статей, посвященных математике (на протяжении 25 лет он вел колонку математических игр и фокусов в журнале «Scientific America»), а также фантастических рассказов и эссе на самые разные темы. В сборник «Когда ты была рыбкой, головастиком — я…» вошли статьи, посвященные вопросам, явлениям или событиям, особенно взволновавшим писателя в последние годы.
Книга известного американского популяризатора науки Мартина Гарднера, посвященная логическим и математическим парадоксам.Рассчитана на самый широкий круг читателей.
Первый перевод с французского книги «Recoltes et Semailles» выдающегося математика современности Александра Гротендика. Автор пытается проанализировать природу математического открытия, отношения учителя и учеников, роль математики в жизни и обществе. Текст книги является философски глубоким и нетривиальным и носит характер воспоминаний и размышлений. Книга будет интересна широкому кругу читателей — математикам, физикам, философам и всем интересующимся историческими, методическими и нравственными вопросами, связанными с процессом математического открытия и возникновения новых теорий.
Давид Гильберт намеревался привести математику из методологического хаоса, в который она погрузилась в конце XIX века, к порядку посредством аксиомы, обосновавшей ее непротиворечиво и полно. В итоге этот эпохальный проект провалился, но сама попытка навсегда изменила облик всей дисциплины. Чтобы избавить математику от противоречий, сделать ее «идеальной», Гильберт исследовал ее вдоль и поперек, даже углубился в физику, чтобы предоставить квантовой механике структуру, названную позже его именем, — гильбертово пространство.
Саймон Сингх рассказывает о самых интересных эпизодах мультсериала, в которых фигурируют важнейшие математические идеи – от числа π и бесконечности до происхождения чисел и самых сложных проблем, над которыми работают современные математики.Книга будет интересна поклонникам сериала «Симпсоны» и всем, кто увлекается математикой.На русском языке публикуется впервые.
Цель книги доктора философских наук Б. В. Бирюкова и кандидата философских наук В. Н. Тростникова - создать общую картину подготовки и развития логико-математических аспектов кибернетики. Авторы рассказывают о длительном развитии науки логики, возникшей еще в Древней Греции, прослеживают непрерывающуюся нить преемственности, тянущуюся от Аристотеля к "чуду XX века" - быстродействующим кибернетическим устройствам.
На протяжении многих веков симметрия оставалась ключевым понятием для художников, архитекторов и музыкантов, однако в XX веке ее глубинный смысл оценили также физики и математики. Именно симметрия сегодня лежит в основе таких фундаментальных физических и космологических теорий, как теория относительности, квантовая механика и теория струн. Начиная с древнего Вавилона и заканчивая самыми передовыми рубежами современной науки Иэн Стюарт, британский математик с мировым именем, прослеживает пути изучения симметрии и открытия ее основополагающих законов.
Сколько имеется простых чисел, не превышающих 20? Их восемь: 2, 3, 5, 7, 11, 13, 17 и 19. А сколько простых чисел, не превышающих миллиона? Миллиарда? Существует ли общая формула, которая могла бы избавить нас от прямого пересчета? Догадка, выдвинутая по этому поводу немецким математиком Бернхардом Риманом в 1859 году, для многих поколений ученых стала навязчивой идеей: изящная, интуитивно понятная и при этом совершенно недоказуемая, она остается одной из величайших нерешенных задач в современной математике.