Оптимальный поиск двух активных шаров на множестве заданных

Рассматриваются задачи поиска двух активных шаров на множестве заданных для n = 31, 44. Приводятся теоремы, по которым можно определить, какое оптимальное количество шагов необходимо для поиска 2-х активных шаров из заданного множества. Для каждого случая описываются конкретные алгоритмы действий. Р...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Теорія оптимальних рішень
Дата:	2015
Автори:	Донец, Г.А., Билецкий, В.И., Ненахов, Э.И.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/112410
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Оптимальный поиск двух активных шаров на множестве заданных / Г.А. Донец, В.И. Билецкий, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 134-139. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-112410
record_format	dspace
spelling	Донец, Г.А. Билецкий, В.И. Ненахов, Э.И. 2017-01-20T21:52:08Z 2017-01-20T21:52:08Z 2015 Оптимальный поиск двух активных шаров на множестве заданных / Г.А. Донец, В.И. Билецкий, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 134-139. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/112410 519.8 Рассматриваются задачи поиска двух активных шаров на множестве заданных для n = 31, 44. Приводятся теоремы, по которым можно определить, какое оптимальное количество шагов необходимо для поиска 2-х активных шаров из заданного множества. Для каждого случая описываются конкретные алгоритмы действий. Розглядуються задачі пошуку двох активних кульок на множині заданих для n = 31, 44. Приводяться теореми, за якими можна визначити, яка оптимальна кількість кроків потрібна для пошуку 2-х активних кульок із заданої множини. Для кожного випадку описуються конкретні алгоритми дій. The problem of searching for two active balls on a given set of n balls is considered for n = 31 and n = 44. We give some theorems that allow calculating the optimal number of steps to find two active balls among the elements of a given set. For every case, the specific algorithms are given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Оптимальный поиск двух активных шаров на множестве заданных Оптимальний пошук двох активних кульок на множині заданих Optimal search for two active balls on a given set Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Оптимальный поиск двух активных шаров на множестве заданных
spellingShingle	Оптимальный поиск двух активных шаров на множестве заданных Донец, Г.А. Билецкий, В.И. Ненахов, Э.И.
title_short	Оптимальный поиск двух активных шаров на множестве заданных
title_full	Оптимальный поиск двух активных шаров на множестве заданных
title_fullStr	Оптимальный поиск двух активных шаров на множестве заданных
title_full_unstemmed	Оптимальный поиск двух активных шаров на множестве заданных
title_sort	оптимальный поиск двух активных шаров на множестве заданных
author	Донец, Г.А. Билецкий, В.И. Ненахов, Э.И.
author_facet	Донец, Г.А. Билецкий, В.И. Ненахов, Э.И.
publishDate	2015
language	Russian
container_title	Теорія оптимальних рішень
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Оптимальний пошук двох активних кульок на множині заданих Optimal search for two active balls on a given set
description	Рассматриваются задачи поиска двух активных шаров на множестве заданных для n = 31, 44. Приводятся теоремы, по которым можно определить, какое оптимальное количество шагов необходимо для поиска 2-х активных шаров из заданного множества. Для каждого случая описываются конкретные алгоритмы действий. Розглядуються задачі пошуку двох активних кульок на множині заданих для n = 31, 44. Приводяться теореми, за якими можна визначити, яка оптимальна кількість кроків потрібна для пошуку 2-х активних кульок із заданої множини. Для кожного випадку описуються конкретні алгоритми дій. The problem of searching for two active balls on a given set of n balls is considered for n = 31 and n = 44. We give some theorems that allow calculating the optimal number of steps to find two active balls among the elements of a given set. For every case, the specific algorithms are given.
issn	XXXX-0013
url	https://nasplib.isofts.kiev.ua/handle/123456789/112410
citation_txt	Оптимальный поиск двух активных шаров на множестве заданных / Г.А. Донец, В.И. Билецкий, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 134-139. — рос.
work_keys_str_mv	AT donecga optimalʹnyipoiskdvuhaktivnyhšarovnamnožestvezadannyh AT bileckiivi optimalʹnyipoiskdvuhaktivnyhšarovnamnožestvezadannyh AT nenahovéi optimalʹnyipoiskdvuhaktivnyhšarovnamnožestvezadannyh AT donecga optimalʹniipošukdvohaktivnihkulʹoknamnožinízadanih AT bileckiivi optimalʹniipošukdvohaktivnihkulʹoknamnožinízadanih AT nenahovéi optimalʹniipošukdvohaktivnihkulʹoknamnožinízadanih AT donecga optimalsearchfortwoactiveballsonagivenset AT bileckiivi optimalsearchfortwoactiveballsonagivenset AT nenahovéi optimalsearchfortwoactiveballsonagivenset
first_indexed	2025-11-25T23:07:35Z
last_indexed	2025-11-25T23:07:35Z
_version_	1850575598120861696
fulltext	134 Теорія оптимальних рішень. 2015 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Рассматриваются задачи поиска двух активных шаров на множе- стве заданных для n = 31, 44. Приводятся теоремы, по кото- рым можно определить, какое оптимальное количество шагов необходимо для поиска 2-х актив- ных шаров из заданного множе- ства. Для каждого случая описы- ваются конкретные алгоритмы действий.  Г.А. Донец, В.И. Билецкий, Э.И. Ненахов, 2015 УДК 519.8 Г.А. ДОНЕЦ, В.И. БИЛЕЦКИЙ, Э.И. НЕНАХОВ ОПТИМАЛЬНЫЙ ПОИСК ДВУХ АКТИВНЫХ ШАРОВ НА МНОЖЕСТВЕ ЗАДАННЫХ Эта задача появилась впервые в 1966 году на Московской математической олимпиаде в такой постановке. Задача. Среди n биллиардных шаров нахо- дятся два радиоактивных. Для любого набора шаров за одну проверку можно узнать, имеется ли в нем хотя бы один радиоактив- ный (но нельзя узнать сколько их). Необ- ходимо за минимальное количество проверок обнаружить два радиоактивных шара. Введем обозначения четырех функций, которые пригодятся для дальнейших рассуж- дений при решении задач поиска 2-х радио- активных (далее активных) шаров: 1( )f n – минимальное число проверок для обнаружения одного активного шара из n заданных; 2( )f n – минимальное число проверок для обнаружения двух активных шаров из n заданных; 1 2( , )g n n – минимальное число проверок для обнаружения двух активных шаров, кото- рые находятся по одному в двух подмножест- вах из 1n и, соответственно, 2n шаров; 1 2( , )h n n – минимальное число проверок для обнаружения двух активных шаров у двух подмножеств, если проверка первого подмно- жества дала положительный результат. Легко  Донец Г.А., Билецкий В.И., Ненахов Э.И. Графо- вый поход к решению задачи поиска радиоактивных шаров // Теорія оптимальних рішень. – К.: Ін-т кібернетики імені В.М. Глушкова НАН України. – 2014. – С. 147 – 154. ОПТИМАЛЬНЫЙ ПОИСК ДВУХ АКТИВНЫХ ШАРОВ ... Теорія оптимальних рішень. 2015 135 подсчитать количество вариантов для последней функции. Это количество равно 1 2 1 2 .nm n n C   По методу, основанному на теории графов, m – это число ребер графа, состоящего из декартового произведения вершин 1n и 2n в совокупности с полным 1n -вершинным графом. Если из s2 шаров активный один, то его можно найти за s проверок. На первом шаге проверяется половина шаров, а затем методом дихотомии проверя- ется то множество шаров, где находится активный шар. Это приводит к формуле    nnf 21 log . Отсюда вытекает неравенство  1 2 2 1 2 2, log logg n n n n  , причем, как оказывается, возможно и строгое неравенство, о чем утверждают следующие леммы. Лемма 1. 4)5,3( g . Результаты проверки обозначим знаками « + » или « – », а саму проверку в виде скобок из уголков. Шаг 1. Вначале берем по одному шару из каждой группы < 1,1 >. Если 1,1 ,  то активные шары находим из оставшихся за 3)4()2( 11  ff провер- ки, а в сумме получаем 4 проверки. Шаг 2. Если 1,1 ,  то проверяем оставшиеся четыре шара < 4 > из группы пяти шаров. Если 4 ,  то пятый шар из этой группы неактивный, а активный один из этой четверки. Его можно обнаружить за 2)4(1 f проверки, и в сумме получается 4 проверки. Шаг 3. Если 4 ,  то активный пятый шар, а второй активный шар находится из группы тройки шаров за 2)3(1 f проверки, что тоже в сумме дает 4 проверки, хотя и    5log3log4 22  . Лемма 2. (5, 5) 5.g  Шаг 1. Берем для проверки по одному шару из каждой группы < 1,1 >. Если результат отрицателен, т. е. 1,1 ,  то тогда из оставшихся шаров в груп-пах активные обнаружим за 4)4,4( g проверки и в сумме получим число про- верок, равное 5. Шаг 2. Если 1,1 ,  то осуществляем проверку < 4 > оставшихся шаров из какой-то группы, например, второй. Шаг 3. Если 4 ,  то 5-й шар в этой группы неактивный, а активный шар из первой группы, который был взят для проверки на 1-м шаге. Второй активный шар находим за 2)4(1 f проверки из второй группы. В сумме полу- чим 4 проверки. Шаг 4. Если 4 ,  то активный 5-й шар этой группы, а второй активный шар найдем из пяти первой группы за 3)5(1 f проверок. В сумме получим число проверок, равное 5. Г.А. ДОНЕЦ, В.И. БИЛЕЦКИЙ, Э.И. НЕНАХОВ 136 Теорія оптимальних рішень. 2015 Лемма 3. 6)9,7( g . Шаг 1. Берем 3 шара из первой группы и 1 из второй группы и осуществим проверку 3,1 .  Если 3,1 ,  то оставшиеся активные шары находим за 5)8()4( 11  ff проверок, а в сумме получим 6. Шаг 2. Если 3,1 ,  то проверяем оставшиеся 8 шаров из второй группы. Если 8 ,  то активный шар тот, который взятый из этой группы для  1,3 . Второй активный шар находится из 7 шаров первой группы за 3)7(1 f испыта- ния, и в сумме число проверок равно 5. Шаг 3. Если 8 ,  то активный шар из 8 находится за 3)8(1 f проверок. Второй активный шар находится среди трех в  1,3 и его можно найти за 2)3(1 f проверки. В сумме получится 1 + 3 + 2 = 6 проверок, а не 1(7)f  1(9) 7.f  Лемма 4. 6)11,5( g . Пронумеруем шары (и отметим номера жирным шрифтом) от 1 до 5 первой группы и от 6 до 16 второй группы. Шаг 1. Берем 1 шар из первой группы, например, 5 и 3 шара из второй группы, например, 6,7,8 и осуществим проверку < 1, 3 >, или (в записи за номе- рами)  8765 ,,, . Если 1,3 ,  получим 5)8,4( g , что в сумме дает 6 проверок. Шаг 2. Если  31, , то осуществляем проверку  65, . Если  65, , то один активный шар среди двух (7 или 8), а другой – среди четырех первой группы. Их можно обнаружить за 3)4,2( g проверки, что в сумме дает число проверок 5. Шаг 3. В случае  65, берем шары  16109 ...,,, . В случае  16109 ...,,, шары  876 ,, неактивны, следовательно, активный 5-й шар, а второй активный шар находим за 3)8(1 f проверок, что в сумме дает 6 проверок. Шаг 4. Если  16109 ...,,, , то проверяем шары  4321 ,,, . В случае  4321 ,,, 5-й шар не активен, а активный 6-й шар. Второй активный шар находим за 2)4(1 f проверки, что в сумме дает 6 проверок. Шаг 5. В случае  4321 ,,, активным является 5-й шар, а второй актив- ный шар найдем среди трех ( 876 ,, ) за 2)3(1 f проверки, что, снова таки, в сумме дает 6 проверок. Лемма 5. 7)11,11( g . Пронумеруем шары (и отметим номера жирным шрифтом) первой группы от 1 до 11 и второй группы – от 12 до 22. Шаг 1. Берем по 3 шара из каждой группы, например, 1, 2, 3 – из первой группы и 12, 13, 14 – из второй группы и осуществляем < 3, 3 >. Если  3,3 , то активные шары найдем за 6)8,8( g проверок, что в сумме дает 7 проверок. ОПТИМАЛЬНЫЙ ПОИСК ДВУХ АКТИВНЫХ ШАРОВ ... Теорія оптимальних рішень. 2015 137 Шаг 2. 3,3 .  Образуем и проверим группу из 3-х шаров  1221 ,, . Если  1221 ,, , переходим к шагу 3. Шаг 3. Проверяем группу шаров  221615 ,...,, . Если  221615 ,...,, , то шары 12, 13, 14 не активные, а активный один среди шаров 1, 2, а второй активный – в группе шаров  221615 ,...,, , который можно обнаружить за 4)8,2( g проверки, что в сумме дает 7 проверок. Шаг 4. Если  221615 ,...,, , то один активный шар находится среди шаров 12, 13, 14. Шаг 5. Проверяем группу шаров  1154 ,...,, . Если  1154 ,...,, , то шары 1, 2, 3 не активны, а активный шар 12. Второй активный шар находим из совокупности  1154 ,...,, за 3)8(1 f проверки, а в сумме получается 7 проверок. Если  1154 ,...,, , то активный шар находится среди  321 ,, , а второй – среди  141312 ,, . Дальше, беря во внимание  1221 ,, , поступаем следующим образом. Шаг 6. Проверяем шар 12. Если 12 , то второй активный шар находим из  321 ,, за 2)3(1 f проверки, а всего получится 7 проверок. Шаг 7. Если 12 , то первый активный находим за одну проверку среди шаров 1,2, а второй – за одну проверку среди шаров 13, 14. В сумме получается 7 проверок. Если  1221 ,, , переходим к шагу 8. Шаг 8. Проверяем группу шаров  1154 ,...,, . Если  1154 ,...,, , то шар 3 не активный, тогда в этом случае, один активный шар – в группе  1154 ,...,, , другой активный шар либо 13, либо 14 (см.  3,3 ). Их можно найти за 4)2,8( g проверок, что в сумме получается 7 проверок. Шаг 9. Если  1154 ,...,, , то активный шар 3, а второй активный шар находим из группы 10 шаров  221413 ,...,, за 4)10(1 f проверки, что в сумме получится 7 проверок. Лемма доказана. Лемма 6. 8)19,13( g . Шаг 1. Берем 5 шаров из первой группы и 3 шара из второй группы и осуществляем проверку  3,5 . Если  3,5 , то активные находим среди оставшихся шаров в группах за 7)9()7( 11  ff проверок и в сумме число проверок равно 8. Шаг 2. Если  3,5 , то из совокупности этих шаров осуществляем проверку  3,1 . Если  3,1 , то активные шары ищем среди четырех оставшихся из группы пяти шаров и среди 16 остальных из второй группы. Их находим за 6)16()4( 11  ff проверок, а в сумме получается 8 проверок. Г.А. ДОНЕЦ, В.И. БИЛЕЦКИЙ, Э.И. НЕНАХОВ 138 Теорія оптимальних рішень. 2015 Шаг 3. Если  3,1 , то из этой совокупности осуществляем проверку  1,1 . Если  1,1 , то активный шар находится среди двух из второй группы, взятых для проверки  3,1 . Его находим за одну проверку ( 1)2(1 f ), а второй шар находим из 12-и шаров первой группы за 4)12(1 f проверки. В сумме получается 8 проверок. Шаг 4. Если  1,1 , то осуществляем проверку 16 из оставшихся шаров второй группы. Если 16 , то 3 шара, ранее проверяемые из этой группы, неактивны. Тогда из  1,1 следует, что в первой группе единственный активный шар определен. Активный шар из второй группы находим за 4)16(1 f проверок. В сумме получим число проверок, равным 8. Шаг 5. Если 16 , то осуществляем проверку 8 из остальных шаров первой группы. Если 8 , то остальные шары этой группы неактивны, а активный второй шар из второй группы в проверке  1,1 . В первой группе за 3)8(1 f проверок находим второй активный шар. В сумме получается 8 проверок. Шаг 6. Если 8 , то осуществляем в этой же группе проверку  4 . Если  4 , то шар из второй группы в проверке  1,1 активен и для нахождения второго активного шара остается 2)4(1 f проверки, что в итоге дает число проверок, равное 8. Шаг 7. Если  4 , то 13-й шар первой группы активен, а второй активный шар находим среди оставшихся трех шаров второй группы за 2)3(1 f проверок, что в итоге дает число проверок, равное 8. Как видно, во всех случаях число проверок равно 8, а не 954)19()13( 11  ff . Тем самым, лемма доказана. Из доказательства этих трех лемм вытекает следующее равенство: 2 1 2 2 1 2(2 ,2 ) ( , ).k lg n n k l g n n     (1) Теорема 1. 9)31(2 f . Шаг 1. Берем 9 шаров и осуществляем проверку  9 . Если  9 , то известно [1], что 8)22(2 f , т. е. из остальных 22 шаров 2 активных можно обнаружить за 8 проверок. Если  9 , то приходим к функции )22,9( h с числом вариантов .2234229 82 9 Cm Шаг 2. Берем 14 шаров из 22 и осуществляем проверку 14 . Если 14 , то получим 7)14,9( g , что в сумме дает 9 проверок. Если 14 , то приходим к функции )8,9( h с числом вариантов .210889 72 9 Cm ОПТИМАЛЬНЫЙ ПОИСК ДВУХ АКТИВНЫХ ШАРОВ ... Теорія оптимальних рішень. 2015 139 Шаг 3. Берем 7 шаров из 8 и осуществляем проверку  7 . Если  7 , то получаем 6)7,9( g , что в сумме дает 9 проверок. Если  7 , то остается 10 шаров, для которых 6)10(2 f , что в сумме дает 9 проверок. Теорема 2. 10)44(2 f . Шаг 1. Берем 13 шаров и осуществляем проверку 13 . Если 13 , то 2 шара из 31 можно найти за 9 проверок (теорема 1), а в сумме получается 10 проверок. Если 13 , то приходим к функции )31,13( h с числом вариантов .24813113 92 13 Cm Шаг 2. Берем 19 шаров из 31 и осуществляем проверку 19 . Если 19 , то получаем 8)19,13( g проверок (лемма 6), а в сумме получим 10 проверок. Если 19 , то приходим к функции )12,13( h с числом вариантов .22341213 82 13 Cm Шаг 3. Берем 5 шаров из первой группы и остальные 20 (8+12) шаров и осуществляем проверку  20,5 . Если  20,5 , то приходим к функции )20,5( h с числом вариантов .2110205 72 5 Cm Шаг 4. Берем 11 шаров из 20 и осуществляем проверку 11 . Если 11 , то по лемме 4 получаем 6)11,5( g проверок, а в сумме получим 10 проверок. Если 11 , то приходим к функции )9,5( h с числом вариантов .25595 62 5 Cm Шаг 5. Проверяем 4 шара из 9. Если  4 , то 2 активных шара получаем за 5)5,5( g проверок. При  4 2 активных шара получим тоже за 5 проверок. В сумме получим 10 проверок. Г.П. Донець, В.І. Білецький, Е.І. Ненахов ОПТИМАЛЬНИЙ ПОШУК ДВОХ АКТИВНИХ КУЛЬОК НА МНОЖИНІ ЗАДАНИХ Розглядуються задачі пошуку двох активних кульок на множині заданих для n = 31, 44. Приводяться теореми, за якими можна визначити, яка оптимальна кількість кроків потрібна для пошуку 2-х активних кульок із заданої множини. Для кожного випадку описуються конкретні алгоритми дій. G.A. Donets, V.I. Biletsky, E.I. Nenakhov OPTIMAL SEARCH FOR TWO ACTIVE BALLS ON A GIVEN SET The problem of searching for two active balls on a given set of n balls is considered for n = 31 and n = 44. We give some theorems that allow calculating the optimal number of steps to find two active balls among the elements of a given set. For every case, the specific algorithms are given. Получено 05.03.2015

Оптимальный поиск двух активных шаров на множестве заданных

Репозитарії

Схожі ресурси