Цепочки Бусины В8 А12, А12к. Задача 28 (Вовк) Цепочки символов (строки) создаются по следующему правилу: первая строка состоит из одного символа, это. - презентация

1 Цепочки Бусины В8 А12, А12к

2 Задача 28 (Вовк) Цепочки символов (строки) создаются по следующему правилу: первая строка состоит из одного символа, это цифра 1. Каждая из следующих цепочек создается так: дважды записывается вся цепочка цифр из предыдущей строки, а в конец приписывается еще одно число – номер строки по порядку (на i шаге дописывается число i). Первые 4 строки, созданные по этому правилу, выглядят следующим образом: 1) 1 2) 112 3) ) Сколько раз в общей сложности встречаются в 7-й строке нечетные цифры (1,3, 5, 7,9)? Решение: В 1-й строке встречается только цифра 1 – 1 раз. Во 2-й строке цифра 1 встречается 2 раза. В каждой следующей строке количество цифр 1 будет удваиваться. В строке с номером k цифра 1 встретится 2 k-1 раз. Аналогичные рассуждения можно провести для всех других нечетных цифр. Нечетная цифра n встречается в строке с номером n 1 раз. В строке с номером k (k>=n) эта цифра встретится 2 k-n раз. Подсчитаем, сколько раз в общей сложности встречаются в седьмой строке нечетные цифры: =85. Ответ:85.

3 Задача 1 (Поляков) Цепочки символов (строки) создаются по следующему правилу: Первая строка состоит из одного символа – цифры «1». Каждая из последующих цепочек создается такими действиями: в начало записывается число – номер строки по порядку (для i-й строки ставится число «i»), далее дважды подряд записывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 211 (3) (4) Сколько раз встречается цифра «1» в первых семи строках (суммарно)? Ответ: =127

4 Задача 2 (Поляков) Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа – цифры «1». Каждая из последующих цепочек создается следующим действием: в очередную строку дважды записывается предыдущая цепочка цифр (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»). Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 112 (3) (4) Сколько раз в общей сложности встречаются в восьмой строке четные цифры (2, 4, 6, 8)? Ответ: 85= В строке с номером k (k>=n) эта цифра n встретится 2 k-n раз.

5 Задача 5 (Поляков) 32 (Вовк) Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа, это цифра 1. Каждая из следующих цепочек создается так. Сначала записывается порядковый номер данной строки, далее дважды записывается вся цепочка цифр из предыдущей строки. Первые 4 строки, созданные по этому правилу, выглядят следующим образом: Сколько раз в общей сложности встречаются в 10-й строке четные цифры (0, 2, 4, 6, 8)? Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа – цифры «1». Каждая из последующих цепочек создается следующим действием: в очередную строку дважды записывается предыдущая цепочка цифр (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»). Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 112 (3) (4) Сколько раз в общей сложности встречаются в десятой строке четные цифры (2, 4, 6, 8)? Ответ: 341 Ответ: 340

6 Задача 29 (Вовк) Цепочки символов (строки) создаются по следующему правилу: первая строка состоит из одного символа, это цифра 1. Каждая из следующих цепочек создается так: дважды записывается вся цепочка цифр из предыдущей строки, а в конец приписывается еще одно число – номер строки по порядку (на i шаге дописывается число i). Первые 4 строки, созданные по этому правилу, выглядят следующим образом: 1) 1 2) 112 3) ) Какая цифра стоит в восьмой строке на 250-м месте (считая слева направо)? Решение: Найдем длину 8 строки. По условию длина каждой следующей строки увеличивается в 2 раза по сравнению с предыдущей плюс 1. 1) 1 элемент 2) 1*2+1=3 3) 3*2+1=7 4) …количество символов 2 i - 1 8) 127*2+1=255. Требуется найти 250-й элемент, т.е. 6-й с конца. Но последние 8 символов 8-й строки будут Ответ: 3

7 Задача 3 (Поляков) Записано 7 строк, каждая имеет свой номер – от «0»- до «6»-й. В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 6 шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i). Для удобства в скобках пишется номер строки (начиная с 0). Ниже показаны первые строки, сформированные по описанному правилу: (0) 0 (1) 001 (2) (3) Какая цифра стоит в последней строке на 123-м месте (считая слева направо)? Ответ: 2 В 6-й строке (2 i+1 – 1) =127 символов, последние

8 Задача 7 (Поляков) В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 9 шагов выполняется следующая операция: в очередную строку дважды записывается предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i). Для удобства в скобках пишется номер строки (начиная с 0). Ниже показаны первые строки, сформированные по описанному правилу: (0) 0 (1) 001 (2) (3) Какая цифра стоит в последней строке на 1022-м месте (считая слева направо)? Ответ: 8 В 9 строке (2 i+1 – 1) =1023 символа, последние

9 Задача из примера (Поляков) Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) BAA (3) CBAABAA (4) DCBAABAACBAABAA Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо). Решение: длины первых строк 1, 3, 7, 15, … – это числа вида 2 i -1, где i – номер строки; таким образом, длина 7-ой строки – 127, а длина восьмой – 255 символов восьмая строка строится так: восьмая буква латинского алфавита (H) и затем – два раза седьмая строка (сверху написаны номера символов) символы находятся на границе двух цепочек, повторяющих 7-ую строку; заметим, что в соответствии с заданным алгоритмом можно легко определить первые символы в 7-ой строке (GFEDC) и последние символы (AABAA). далее сразу находим, что интересующая нас часть 8-ой строки имеет вид A B A A G F E D C HGFEDC…...AABAAGFEDC…...AABAA Ответ: BAAGFED.

10 Задача 30 (Вовк) Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) BAA (3) CBAABAA (4) DCBAABAACBAABAA Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите восемь символов подряд, стоящие в шестой строке с 55-го по 62-е место (считая слева направо). Ответ: AAСВААВА.

11 Задача 10 (Поляков) Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней слева дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) AAB (3) AABAABC (4) AABAABCAABAABCD Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите семь символов подряд, стоящие в седьмой строке со 118-го по 124-е место (считая слева направо). Ответ: ABAABCD.

12 Задача 11 (Поляков) Строки (цепочки символов из букв русского алфавита) создаются по следующему правилу. Первая строка состоит из одного символа – буквы «А». Каждая из последующих цепочек создается следующим действием: в очередную строку дважды записывается предыдущая строка (цепочка за цепочкой, подряд), а в конец приписывается еще один символ – чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге дописывается «i»-я буква алфавита). Вот первые 4 строки, созданные по этому правилу: (1) А (2) ААБ (3) ААБААБВ (4) ААБААБВААБААБВГ Начальная часть русского алфавита (для справки): А Б В Г Д Е Ё Ж З И Й К … Сколько раз в общей сложности встречаются в восьмой строке согласные буквы (Б, В, Г, Д, Ж, З, К, …)? Ответ: 121.

13 Задача 12 (Поляков) Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней слева дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) AAB (3) AABAABC (4) AABAABCAABAABCD Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите шесть символов подряд, стоящие в седьмой строке со 120-го по 125-е место (считая слева направо). Ответ: AABCDE.

14 Задачи для тренировки (Поляков) 4. Цепочки символов (строки) создаются по следующему правилу: первая строка состоит из одного символа, это цифра 1. Каждая из следующих цепочек создается так: сначала записывается порядковый номер данной строки, далее дважды записывается вся цепочка цифр из предыдущей строки. Первые 4 строки, созданные по этому правилу, выглядят следующим образом: Сколько раз в общей сложности встречаются в 10-й строке нечетные цифры (1,3, 5, 7,9)? 6. Цепочки символов (строки) создаются по следующему правилу: в начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 9 шагов выполняется следующая операция: в очередную строку дважды записывается предыдущая строка, а в конец строки приписывается очередная цифра (на n-м шаге приписывается цифра n.). Ниже показаны первые строки, сформированные по описанному правилу (в скобках записан номер строки, начиная с 0). (0)0 (1)001 (2) (3) Сколько раз встретится цифра 1 в последней строке? 9. Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа, это цифра 1. Каждая из следующих цепочек создается так. Сначала записывается порядковый номер данной строки, далее дважды записывается вся цепочка цифр из предыдущей строки. Первые 4 строки, созданные по этому правилу, выглядят следующим образом: Сколько раз в общей сложности встречается в 9-й строке цифра 1? Ответ: 683 Ответ: 256

15 Бусины(базовый уровень, время – 2 мин) Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин A, B, C. На первом месте – одна из бусин B, D, C, которой нет на третьем месте. В середине – одна из бусин А, C, E, B, не стоящая на первом месте. Какая из перечисленных цепочек создана по этому правилу? 1) CBB2) EAC 3)BCD 4) BCB Ответ: 1).

16 Задача 2 (Поляков) Для составления цепочек разрешается использовать бусины 5 типов, обозначаемых буквами А, Б, В, Е, И. Каждая цепочка должна состоять из трех бусин, при этом должны соблюдаться следующие правила: а) на первом месте стоит одна из букв: А, Е, И, б) после гласной буквы в цепочке не может снова идти гласная, а после согласной – согласная, в) последней буквой не может быть А. Какая из цепочек построена по этим правилам? 1)АИБ 2) ЕВА3) БИВ4) ИБИ Ответ: 4).

17 Задача 5 (Поляков) Для составления 4-значных чисел используются цифры 1, 2, 3, 4, 5, при этом соблюдаются следующие правила: На первом месте стоит одна из цифр 1, 2 или 3. После каждой четной цифры идет нечетная, а после каждой нечетной - четная Третьей цифрой не может быть цифра 5. Какое из перечисленных чисел получено по этим правилам? 1) 43252) ) ) 3452 Ответ: 2).

18 Задача 7 (Поляков) Для составления цепочек используются разноцветные бусины: темные – синяя (С), зеленая (3) и светлые – желтая (Ж), белая (Б), голубая (Г). На первом месте в цепочке стоит бусина синего или желтого цвета. В середине цепочки – любая из светлых бусин, если первая бусина темная, и любая из темных бусин, если первая бусина светлая. На последнем месте – одна из бусин белого, голубого или зеленого цвета, не стоящая в цепочке в середине. Какая из перечисленных цепочек создана по этому правилу? 1) ЖСГ2) БГЗ 3) СГЖ4) ЖБС Ответ: 1).

19 Задача 12 (Поляков) Кассир забыл пароль к сейфу, но помнил алгоритм его получения из строки «AYY1YABC55»: если последовательно удалить из строки цепочки символов «YY» и «ABC», а затем поменять местами символы A и Y, то полученная последовательность и будет паролем. Определите пароль: 1) A1Y552) A1553) A55Y14) Y1A55 Ответ: 4).

20 A12к расчет количества возможных вариантов (комбинаторика) Что нужно знать: если на каждом шаге известно количество возможных вариантов выбора, то для вычисления общего количества вариантов нужно все эти числа перемножить; например, в двузначном числе мы можем выбрать первую цифру 9 способами (она не может быть нулем), а вторую – 10 способами, поэтому всего есть 9·10=90 двузначных чисел если мы разбили все нужные нам комбинации на несколько групп (не имеющих общих элементов!) и подсчитали количество вариантов в каждой группе, то для вычисления общего количества вариантов нужно все эти числа сложить; например, есть 9·10=90 трехзначных чисел, оканчивающихся на 5, и 9·10=90 трехзначных чисел, оканчивающихся на 2, поэтому 90+90=180 трехзначных чисел оканчиваются на 2 или на 5 если в предыдущем случае группы имеют общие элементы, их количество нужно вычесть из полученной суммы; например, есть 9·10=90 трехзначных чисел, оканчивающихся на 5, и 10·10=100 трехзначных чисел, начинающихся на 5; в обе группы входят числа, которые начинаются и заканчиваются на 5, их всего 10 штук, поэтому количество чисел, которые начинаются или заканчиваются на 5, равно =180.

21 Что не мешает знать: если есть n различных элементов, число их различных перестановок равно факториалу числа n, то есть произведению всех натуральных чисел от 1 до n: n! = 1·2·3·…·(n-1)·n например, три объекта (А, Б и В) можно переставить 6 способами (3!=1·2·3=6): (А, Б, В), (А, В, Б), (Б, А, В), (Б, В, А), (В, А, Б) и (В, Б, А) если нужно выбрать m элементов из n (где n m) и две комбинации, состоящие из одних и тех же элементов, расположенных в разном порядке, считаются различными, число таких комбинаций (они называются размещениями) равно например, в соревновании пяти спортсменов призовые места (первые три) могут распределиться 60 способами, поскольку если нужно выбрать m элементов из n (где n m) и порядок их расположения не играет роли, число таких комбинаций (они называются сочетаниями) равно например, выбрать двух дежурных из пяти человек можно 10 способами, поскольку

22 Задача. Сколько существует различных четырехзначных чисел, в записи которых используются только четные цифры? 1) 1252) 250 3) 5004) 625 Решение: первой цифрой может быть любая четная цифра, кроме нуля (иначе число не будет четырехзначным) – это 2, 4, 6 или 8, всего 4 варианта; предположим, что первая цифра выбрана; независимо от нее на втором месте может стоять любая из четных цифр – 0, 2, 4, 6 или 8, всего 5 вариантов; аналогично находим, что последние две цифры также могут быть выбраны 5-ю способами каждая, независимо друг от друга и от других цифр (первой и второй); общее количество комбинаций равно произведению 4·5·5·5 = 500; правильный ответ – 3.

23 Задача. Сколько существует четырехзначных чисел, в записи которых все цифры различны? 1) 35282) ) 50404) 9000 Решение: первой цифрой может быть любая цифра, кроме нуля (иначе число не будет четырехзначным), всего 9 вариантов; предположим, что первая цифра x выбрана; на втором месте может стоять любая цифра y, кроме x, всего 9 вариантов (ноль тоже может быть!); третья цифра z может быть любой, кроме тех двух, которые уже стоят на первых двух местах, всего 8 вариантов; наконец, четвертая цифра может быть любой из 7 оставшихся (не равных x, y и z); общее количество комбинаций равно произведению 9·9·8·7 = 4536; правильный ответ – 2.

24 Задача. Сколько существует различных четырехзначных чисел, в записи которых ровно две девятки, стоящие рядом? 1) 2122) 225 3) 2434) 280 Решение: возможны три случая: 99, 99 и 99, где жирная точка обозначает некоторую цифру, не равную 9; для каждого из этих случаев нужно подсчитать количество вариантов и эти числа сложить в варианте 99 две последних цифры могут быть любыми, кроме девятки (по 9 вариантов выбора), поэтому всего получаем 1·1·9·9 = 81 вариант; в варианте 99 первая цифра не может быть нулем и девяткой (остается 8 вариантов), а последняя может быть любой, кроме девятки (9 вариантов), поэтому всего получаем 8·1·1·9 = 72 варианта; в варианте 99 первая цифра не может быть нулем и девяткой (остается 8 вариантов), а последняя может быть любой, кроме девятки (9 вариантов), поэтому всего получаем 8·9·1·1 = 72 варианта. общее количество вариантов равно сумме = 225 Правильный ответ – 2.

25 Задача. Сколько существует различных четырехзначных чисел, в записи которых не более двух различных цифр? 1) 4462) 5163) 5764) 640 Решение: обозначим первую цифру через x, она не может быть нулем, поэтому возможно 9 вариантов выбора; другую цифру обозначим через y, ее тоже можно выбирать 9 способами (она может быть нулем, но не может быть равна x); нужно отдельно рассмотреть три случая: xy, xxy и xxx ; для каждого из этих случаев нужно подсчитать количество вариантов и эти числа сложить; в варианте xy две последних цифры могут быть (независимо друг от друга) выбраны равными x или y (по 2 варианта выбора), поэтому всего получаем 9·9·2·2 = 324 варианта; в варианте xxy последняя цифра может быть равна только x или y (2 варианта), поэтому всего получаем 9·1·9·2 = 162 варианта; в варианте xxx последняя цифра может быть любой (10 вариантов), поэтому всего получаем 9·1·1·10 = 90 вариантов; общее количество вариантов равно сумме = 576 Правильный ответ – 3.

26 Задача. Сколько существует различных четырехзначных чисел, в записи которых все цифры нечетные и хотя бы одна из них равна 5? 1) 2262) 3693) 6004) 625 Решение (вариант 1): рассмотрим четыре варианта: 5, 5, 5 и 5; для каждого из этих случаев нужно подсчитать количество уникальных вариантов (исключив все общие!) и эти числа сложить в случае 5 три последних цифры могут быть любыми нечетными (по 5 независимых вариантов выбора), поэтому всего получаем 1·5·5·5 = 125 вариантов; с первого взгляда для случая 5 ситуация та же самая, но это не так; дело в том, что часть этих вариантов (с пятеркой на первом месте) уже вошла в первую группу 5, поэтому второй раз их учитывать не нужно; это значит, что на первом месте может быть одна из 4-х цифр – 1, 3, 7 или 9, всего получаем 4·1·5·5 = 100 вариантов; рассматривая случай 5, нужно выкинуть все варианты, в которых пятерки стоят на первых двух местах. Всего получаем 4·4·1·5 = 80 вариантов; для 5 аналогично получаем 4·4·4·1 = 64 варианта; общее количество вариантов = 369. Правильный ответ – 2.

27 Решение (вариант 2) все числа, состоящие только из нечетных цифр, можно разбить на две группы: те, в которых есть пятерка, и те, где ее нет; общее число чисел, состоящих только из нечетных цифр, находим аналогично первой рассмотренной задаче; учитывая, что среди них нет нуля, получаем 5·5·5·5 = 625 вариантов; теперь аналогично найдем количество чисел, состоящих только из цифр 1, 3, 7 и 9 (без пятерки); поскольку на каждом из 4-х мест может стоять одна из 4-х цифр, получаем 4·4·4·4 = 256 вариантов; нужный нам результат – это разница 625 – 256 = 369 вариантов Правильный ответ – 2.

28 Задача. Виктор хочет купить пять разных книг, но денег у него хватает только на три (любые) книги. Сколькими способами Виктор может выбрать три книги из пяти? 1) 102) 203) 304) 60 Решение: будем рассуждать так: сначала Виктор выбирает одну (любую) книгу, затем – вторую (из оставшихся), затем – третью; у него есть 5 разных способов выбрать первую книгу, затем – 4 разных способа выбрать вторую книгу (поскольку ту, что он выбрал сначала, уже нет смысла брать снова), и 3 способа выбрать третью книгу. Всего получаем 5·4·3 = 60 вариантов; проблема состоит в том, что среди этих 60 вариантов есть повторяющиеся: предположим, что книги имеют номера от 1 до 5, тогда наборы книг (1, 2, 3) и (3, 2, 1) – одинаковые (это разные перестановки чисел 1, 2 и 3); подсчитаем число перестановок трех чисел; на первом месте может стоять любое из 3-х чисел (3 варианта), на втором месте – любое из двух оставшихся (2 варианта), на третьем месте – только одно оставшееся число. Всего получаем 3·2·1 = 6 вариантов. это означает, что каждое сочетание было подсчитано 6 раз в п. 2, поэтому различных сочетаний книг – в 6 раз меньше, то есть 60 / 6 = 10. Правильный ответ – 1.

29 Решение (вариант 2, формулы комбинаторики ) нам нужно выбрать 3 объекта из 5, причем порядок выбора здесь не важен – нам нужны разные сочетания; зная формулу для вычисления количества сочетаний, сразу находим (при m = 3 и n = 5) Правильный ответ – 1.

30 Задачи для тренировки: 1. Сколько существует четырехзначных чисел, в которых есть ровно две восьмерки, не стоящие рядом? 1) 216 2) 224 3) 234 4) 243 Ответ:3 2. Сколько существует четырехзначных чисел, составленных из разных четных цифр? 1) 96 2) 120 3) 500 4) 625 Ответ:1 3. Сколько существует четырехзначных чисел, в записи которых есть хотя бы одна четная цифра? 1) ) ) ) 9000 Ответ:3 4. Сколько существует четырехзначных чисел, которые делятся на 5? 1) 900 2) ) ) 2000 Ответ:3 5. Сколько существует четырехзначных чисел, не превышающих 3000, в которых ровно две цифры «3»? 1) 36 2) 543) 81 4) 162 Ответ:2

31 Задачи для тренировки: 6. В чемпионате по шахматам участвовало 40 спортсменов. Каждый с каждым сыграл по одной партии. Сколько всего партий было сыграно? 1) 780 2) 800 3) ) 1600 Ответ:1 7. В вазе лежат яблоко, груша, персик и абрикос. Кате разрешили выбрать два каких-то фрукта. Сколько у Кати вариантов выбора? 1) 6 2) 12 3) 16 4) 24 Ответ:1 8. У Паши есть 6 воздушных шариков разного цвета. Три из них он хочет подарить Маше. Сколькими способами он может это сделать? 1) 6 2) 123) 20 4) 60 Ответ:3 9. Сколько существует четырехзначных чисел, которые читаются одинаково «слева направо» и «справа налево»? 1) 50 2) 903) 100 4) 120 Ответ:2 10. Цепочка из трех бусин формируется по следующему правилу: На первом месте в цепочке стоит одна из бусин А, Б, В. На втором – одна из бусин Б, В, Г. На третьем месте – одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте. Сколько всего есть таких цепочек? 1) 9 2) 16 3) 21 4) 27 Ответ:2