Комбинаторика в жизнедеятельности человека и решение комбинаторных задач

Представителям самых различных специальностей приходится решать задачи, в которых «рассматриваются те или иные комбинации, составленные из букв, цифр или других объектов» [1, с. 3].

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

Комбинаторика связана со многими другими областями математики – алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например, в генетике, информатике, статистической физике). Термин «комбинаторика» был введён выдающимся немецким математиком Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Теория и практика решения комбинаторных задач на составление автомобильных номеров

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

Регистрационный номер машины – это показатель, применяемый для идентификации автомобильного транспорта. Благодаря целой системе, разработанной уже давно, за счет присвоения индивидуальных номеров каждому автомобилю, все машины легко поставить на регистрационный учет. Затем можно координировать все движения по документации в отношении каких-либо изменений по правовладе-нию машиной, а также фиксировать правонарушения и отслеживать должников и штрафников. Каждый такой номер в первую очередь привязан по территориальному критерию к пункту регистрации, где оформляется машина на собственника [2].

Двух одинаковых номеров существовать не может, так как это является мошенничеством и наказуемо штрафами, а также постановкой автомобиля на штрафную стоянку, в соответствии с законом «Статья 12.2 КоАП РФ. Управление транспортным средством с нарушением правил установки на нем государственных регистрационных знаков» [3]. Номера должны отличаться хотя бы одной цифрой или буквой, либо порядком их расположения.

Кроме этого существует определенный порядок для выдачи государственных номеров.

• 1.    Очень частые изменения в номерах наблюдаются в третьей цифре. И тогда, к примеру, в номере Т480ВМ изменится ситуация на следующую – Т482ВМ.

• 2.    Следом за третьей цифрой по частоте их изменений стоит вторая цифра. Принцип смены этого знака такой же, как и в случае с третьей цифрой.

• 3.    На третьем месте по частоте смен стоит первая цифра регистрационного номера. Она точно так же меняется, как и третья и вторая цифры.

• 4.    Далее в смене символов по частоте изменения стоят буквы, и счет мест продолжается от числа занятых уже мест цифр. Это обозначает, что на четвертом

• 5.    Пятая по частоте изменений – это третья буква. Она меняется по такому же принципу, как и первая буква.

• 6.    Шестая – меняется буква, что стоит второй по счету в номерной аббревиатуре.

месте по частоте изменений стоит буква номера. Например, в номере Т482ВМ изменится буква следующим образом – О482ВМ.

Схема построения регистрационного номера изображена на рисунке 1.

Код региона

Серия

Регистрационный номер

Рис. 1. Схема построения регистрационного номера машины в России

Флаг России

Страна

Исходя из рассмотренных правил, можно составить задачу о числе регистрационных номеров машин.

Задача 1. Рассмотрим регистрационный номер машины определенного региона, состоящий из трех букв и трех цифр, идущих в определенной последовательности: одна буква, три цифры, две буквы. Буквы в государственном номере должны совпадать с буквами латинского алфавита, Сколько существует вариантов регистрационных номеров машин в Нижегородской области?

Решение. В алфавите 33 буквы: А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я. Используются буквы А В Е К М Н О Р С Т У Х (всего 12 вариантов). Так как в номере машины могут повторяться и буквы и цифры, соответственно, используется формула размещение с повторениями An = . Выбираются три буквы из двенадцати возмож- ных. Это можно сделать A12 =12 = 1 728 способами.

Номер машины содержит также три цифры 0 до 9. Используются три цифры из десяти возможных: ^10 =103 =1 000.

Таким образом, для региона 52 общее количество вариантов для составления регистрационного автомобильного знака равно 1000∗1728=1 728 000. Вычисление проводится по правилу умножения, так как номер содержит и буквы и цифры.

Действующую систему номерных знаков машин можно рассмотреть и в Великобритании, которая отличается от российской системы.

Регистрационные номера машин в Великобритании имеют небольшую особенность в цветах: на белом фоне обозначаются передние номера, а на желтом фоне – задние номера.

Схема построения регистрационного номера изображено на рисунке 2.

Идентификатор           Идентификатор срока страны

Серия

Код региона

• Рис. 2 Схема построения регистрационного номера машины в Великобритании

  Задача 2. Действующая система номерных знаков Великобритании была введена в 2001 году. Каждый номер (индексирование номерного знака) состоит из семи знаков. Слева направо знак состоит из следующих символов.

• 1.    Код региона (area code) состоит из двух букв. Первая идентифицирует регион, в котором зарегистрировано транспортное средство, то есть можно использовать буквы следующего вида: A B C D E F G H K L M N O P R S V W Y (всего 19 вариантов). Вторая буква обозначает код офиса регистрации. Для нее используют буквы: A B C D E F G H J K L M N O P R S

• 2.    Двузначный идентификатор срока службы (age identifier). Он меняется два раза в год, в марте и в сентябре. Этот код содержится в двух последних цифрах, либо номер года, (например 05 для 2005), если он был присвоен в интервале с марта по август, либо, если регистрация проходила с сентября по февраль следующего года, то другую цифру, отражающую номер года (к ней будет прибавлено 50). Номер идентификатора действует с 2001 года, значит, эта система существует 18 лет. Схема присваивания идентификатора изображена на рисунке 3.

• 3.    Серия – произвольная комбинация последовательности из трех букв. Для этой комбинации используют только 23 буквы: A B C D E F G H J K L M N O P R S T U V W X Y. Они не должны повторяться.

T U V W X Y (всего 23 варианта). I, Q и Z не используются в данном коде.

Year Год	March Март	September Сентябрь	Year Год	March Март	September Сентябрь
2001	01	51	2026	26	76
2002	02	52	2027	27	77
2003	03	53	2028	28	78
2004	04	54	2029	29	79
2005	05	55	2030	30	80
2006	06	56	2031	31	81
2007	07	57	2032	32	82
2008	08	58	2033	33	83
2009	09	59	2034	34	84
2010	10	60	2035	35	85
2011	11	61	2036	36	86
2012	12	62	2037	37	87
2013	13	63	2038	38	88
2014	14	64	2039	39	89
2015	15	65	2040	40	90
2016	16	66	2041	41	91
2017	17	67	2042	42	92
2018	18	68	2043	43	93

Рис. 3. Идентификаторы срока службы (age identifiers)

Этот набор индивидуален для каждого автомобиля.

Решение. Код региона состоит из двух букв. Как указано в условии, для первой буквы кода будет 19 вариантов. Для второй буквы 23 варианта. По правилу произведения существует 19*23 = 437 комбинаций для кода региона.

Номер идентификатора включается номер автомобиля 18 лет, тогда по правилу произведения будет 18*2 = 36 вариантов, так как существует два периода регистрации номера идентификатора. Если номер получен с марта по август, то оставляют дату выпуска машины, а если регистрация проходила с сентября по февраль, то к году выпуска машины прибавляется число 50.

Так как серия состоит из трех букв, и они не должны повторяться, то можно применить формулу размещение без повторений 4 = ^.

k = 3, n = 23; ^ 3 = 5535,- _S^-10 626 вариантов серий.

Таким образом, в Великобритании может существовать 437*36*10 626 = 167 168 232 номера.

Номер идентификатора имеет два преимущества [4].

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

– В случае если полиция будет проводить расследование несчастного случая или преступления, связанного с данным транспортным средством, свидетели обычно вспомнят начальный шифр на щитке номеров; впоследствии будет проще сузить круг подозреваемых автомобилей до небольшого числа путём проверки по базе данных, без необходимости знать полный номер.

В соответствии с этой схемой номеров должно хватить для регистрации автомобилей до 2050 года.

Задача 3. Найти возможное число автомобильных номеров, в России учитывая, что имеется 85 субъектов.

Решение. Из первой задачи следует, что для одного региона можно составить 1 728 000 номеров. Для 85 субъектов общее количество вариантов для составления регистрационного автомобильного знака равно 1 728 000*85 = 167 168 232 .

По состоянию на 1 июля 2016 года на территории Российской Федерации было зарегистрировано 49,11 млн. единиц автомобильной техники. Большую часть зарегистрированного автопарка, 84%, или примерно 41,08 млн. единиц, составляют легковые автомобили. На легкую коммерческую технику приходится 8% от общего объема (3,95 млн. шт.), на грузовые авто – 7,5% (3,69 млн. шт.), а еще около 1% – на автобусы (0,39 млн. шт.).

Если учесть, что население России составляет примерно 146,5 млн. человек, то окажется, что на 1000 россиян приходится примерно 285 автомобилей, то есть личный автомобиль есть только у каждого 3 – 4 россиянина [5].

Заключение.

Комбинаторика имеет большое значение в различных областях науки и образования. В настоящее время в образовательный стандарт по математике включены основы комбинаторики, решение комбинаторных задач методом перебора, составлением «дерева» вариантов. На комбинаторике основывается теория игр, применяющаяся и для создания «разумных» систем и слежения. Именно комбинаторными методами оценивается устойчивость к взлому систем шифрования аутентификации, в том числе в военных разработках. Усиление интереса к комбинаторике в последнее время обуславливается быстрым развитием кибернетики. В современной комбинаторике и по сей день делаются новые открытия.