Системы счисления олимпиадные задачи

Пример.

1 (результирующие числа по одному в строке)

Задача 8:

Какое наименьшее число гирь необходимо для того, чтобы иметь возможность взвесить любое число граммов от 1 до 100 на чашечных весах, если гири можно класть только на одну чашку весов?

Решение:

Любое число можно записать в двоичной системе счисления. Поэтому для взвешивания любого числа граммов от 1 до 100 достаточно иметь семь гирь с весами: 1, 2, 4, 8, 16, 32, 64. Шестью гирями обойтись нельзя, так как с их помощью можно взвесить не более 2 6 – 1 = 63 различных весов (каждая гиря либо участвует, либо не участвует во взвешивании).

Задача 9:

Какое наименьшее число гирь необходимо для того, чтобы иметь возможность взвесить любое число граммов от 1 до 100 на чашечных весах, если гири можно класть на обе чашки весов.

Решение:

При решении этой задачи нам понадобится следующее интересное свойство троичной системы счисления:

любое натуральное число можно представить в виде разности двух чисел, запись которых в троичной системе счисления содержит только 0 и 1.

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

Теперь понятно, что достаточно иметь 5 гирь с весами 1, 3, 9, 27, 81 (подумайте, почему не нужна гиря весом 243 грамма).

Четырех же гирь явно недостаточно, так как с их помощью можно взвесить не более 3 4 – 1 = 80 различных весов (каждая гиря либо на левой чашке весов, либо на правой, либо не участвует во взвешивании).

Задача 10:

Кащей Бессмертный загадывает три двузначных числа: a, b и c. Иван Царевич должен назвать ему три числа: X, Y, Z, после чего Кащей сообщит ему сумму aX + bY + cZ. Царевич должен отгадать задуманные числа, иначе ему отрубят голову. Как ему спастись?

Решение:

Царевич должен назвать числа 1, 100, 100² = 10000. Числа a, b, c – «цифры» ответа Кащея в 100-ичной записи.

Задача 11:

Докажите, что из набора 0, 1, 2, …, 3 k – 1 можно выбрать 2 k чисел так, чтобы никакое из них не являлось средним арифметическим двух других выбранных чисел.

Решение:

Воспользуемся троичной системой счисления. Будем считать, что троичная запись каждого из данных чисел состоит ровно из k цифр (при необходимости заполним пустующие старшие разряды нулями). Выберем теперь те числа, троичная запись которых содержит только цифры 0 и 1. Очевидно, что их ровно 2 k . Покажем, что это и есть искомый набор. Предположим противное: среди выбранных чисел есть три различных числа x, y, z, удовлетворяющих равенству x + y = 2z. Так как числа x и y различаются хотя бы в одном разряде, то в троичной записи их суммы x + y в этом разряде стоит цифра 1. Однако в записи числа 2z встречаются только 0 и 2.

Задача 12:

Докажите, что из набора 0, 1, 2, …, 3 k – 1 /2 можно выбрать 2 k чисел так, чтобы никакое из них не являлось средним арифметическим двух других выбранных чисел.

Решение олимпиадных задач по теме "Системы счисления"

Скачать:

Предварительный просмотр:

Подписи к слайдам:

По теме: методические разработки, презентации и конспекты

Методика решения олимпиадных задач (презентация).

В условиях предпрофильного обучения учителя химии использу­ют нетрадиционные методики. Сре­ди них урок-практикум для разно­возрастной группы (9-й и 11 -й клас­сы). Это позволяет учащимся 9-х классов б.

P < margin-bottom: 0.21cm; >Занятие рассчитано на учащихся 1 класса и длительностью 35 минут. Это первое занятие в серии занятий «Решение логических задач» к методическому пособию «Логические за.

Психология – особая наука, по ней нет единой общероссийской олимпиады. Поэтому психологи стараются принимать участие со своими ребятами в разных предлагаемых им конкурсах. Наша задача была разработана.

С 2013 года участвую в работе инновационной площадки «Центр дополнительного образования – интегрирующая образовательная среда по работе с одарёнными детьми».Решение задач способствует более глубокому .

Решение олимпиадных задач по теме "Системы счисления&quot.

Даны решения олимпиадных задач по информатике на паскале.