Вот, может кто-нибудь мне растолковать что будет с распределением простых, если пресловутая гипотеза Римана вдруг окажется ошибочной?
с распределением простых ничего не будет, оно каким было, такое и останется
Но будет проблема с очень многими результатами (в том числе и про распределение простых чисел), которые сейчас доказаны в предположении, что Гипотеза Римана верна. Я в теории чисел плохо разбираюсь, но думаю что в некоторых ее разделах наступит небольшой локальный хаос
А библиотекарю потребовалось проделать экспоненциальную работу по упорядочиванию книг наугад, 2^(n-1) - 1, а не полиномиальную, n^2, как нам показалось
А библиотекарю потребовалось проделать экспоненциальную работу по упорядочиванию книг наугад, 2^(n-1) - 1, а не полиномиальную, n^2, как нам показалось
Про оценку наибольшего числа перемещений/сдвигов книг, которые пришлось бы проделать библиотекарю в упрощённой задаче упорядочивания книг на полочке, когда наугад вынимать и ставить на своё место книгу можно лишь налево и значит сдвигать другие остаётся лишь направо.
Вот якобы решение: Сопоставим каждой перестановке книг сумму внизу.
Суммирование ведется по всем книгам, которые стоят на своем месте или левее (кроме самой последней), т.е. по тем книгам, которые нельзя двигать. У суммы есть три свойства: (1) ее минимальное значение - 0; (2) ее максимальное значение - 2^{n-1} - 1; (3) на каждом шаге она возрастает. Это дает оценку числа шагов сверху. Достижима ли она? Сумма равна 0, только если все книги (за исключением последней) стоят правее, чем нужно. Это возможно в одной единственной расстановке: n 1 2 3 ... n-2 n-1. Если на каждом шаге мы ставим на место книгу, стоящую на последнем месте, то полная расстановка как раз и займет 2^{n-1} - 1 шагов.
p.s. Есть и более лобовое доказательство по индукции. Оно основано на следующих соображениях: (1) как только мы поставим книгу 1 на место, задача сведется к предыдущей; (2) книгу, стоящую на первом месте нельзя двигать; (3) пока мы не двигаем книгу 1, мы можем мысленно поменять ее местами с книгой, стоящей на первом месте. Получается следующее: 2^{n-2} - 1 шагов (не трогаем книгу 1) + 1 шаг (ставим книгу 1 на место) + еще 2^{n-2} - 1 шагов (расставляем все остальное) = 2^{n-1} - 1 шагов.
*********************
Три равных окружности имеют общую точку K и лежат внутри треугольника ABC. Каждая из окружностей касается двух сторон треугольника (т.е., одна касается сторон AB и AC, другая AB и BC, а третья AC и BC). Докажите, что точка K лежит на одной прямой с центрами вписанной и описанной окружностей треугольника ABC.
А если к позиции выше 4132 (16 ходов для её упорядочивания) прийти из позиции 4123 за счёт еще 2 хода, то получаем 18 ходов для упорядочивания начальной позиции 4123
Три равных окружности имеют общую точку K и лежат внутри треугольника ABC. Каждая из окружностей касается двух сторон треугольника (т.е., одна касается сторон AB и AC, другая AB и BC, а третья AC и BC). Докажите, что точка K лежит на одной прямой с центрами вписанной и описанной окружностей треугольника ABC.
Запутался я в этих окружностях и прямых иже с ними
Юрик на ЧП намекнул, что я дурак и потому не понимаю доказательства задачи о библиотекаре
. Тем не менее не вижу ничего ошибочного в перестановках сверху, если цель состоит в максимально неэффективном (худшей стратегии) упорядочивании книг. Подсчитывание сколько раз хватаем какую-либо книгу выглядит естественным
Три равных окружности имеют общую точку K и лежат внутри треугольника ABC. Каждая из окружностей касается двух сторон треугольника (т.е., одна касается сторон AB и AC, другая AB и BC, а третья AC и BC). Докажите, что точка K лежит на одной прямой с центрами вписанной и описанной окружностей треугольника ABC.
Запутался я в этих окружностях и прямых иже с ними
Если подумать, то вроде бы просто. Соединим центры окружностей, тогда К - центр описанной окружности нового малого треугольника, причем его стороны паралельны сторонам большого (ввиду равенства окружностей), и более того, биссектрисы большого треугольника проходят через вершины малого ввиду того, что три изначальные окружности касаются сторон большого треугольника, а значит центры вписанных окружностей совпадают. Так как треугольники подобны, то мы можем растянуть плоскость так, что общий центр вписанных окружностей неподвижен, тогда точка К трансформируется (линейно) в центр описанной окружности большого треугольника. Что и требовалось доказать.
Хайдук, а Вы не могли бы запостить строгую формулировку задачи? А то мне непонятно, что Вы пытаетесь сосчитать?
Формулирофка следующая:
Библиотекарь упорядочивает книги на полочке. Наугад вынимает, чтобы поставить на её должное место книгу только, если она лежала справа от своего должного места. Дабы освободить это должное место, библиотекарь начинает сдвигать вправо на одну позицию некоторые книги, начиная очевидно с той, что лежит слева по соседству от только-что освободившегося вынутой книгой места. Ясно, что библиотекарю придётся сдвинуть на одну позицию вправо некоторые книги вплоть до и включительно ту, что лежит на должном месте вынутой книги. Сойдётся ли такой процесс (выбора наугад нележащей на своём должном месте книги) и какое число перемещений книг может понадобиться?
Соединим центры окружностей, тогда К - центр описанной окружности нового малого треугольника, причем его стороны паралельны сторонам большого (ввиду равенства окружностей), и более того, биссектрисы большого треугольника проходят через вершины малого ввиду того, что три изначальные окружности касаются сторон большого треугольника, а значит центры вписанных окружностей совпадают. Так как треугольники подобны, то мы можем растянуть плоскость так, что общий центр вписанных окружностей неподвижен, тогда точка К трансформируется (линейно) в центр описанной окружности большого треугольника. Что и требовалось доказать.
Сойдётся ли такой процесс (выбора наугад нележащей на своём должном месте книги) и какое число перемещений книг может понадобиться?
Означает ли это сколько операций перемещения (перемещается группа книг) или сколько книг будет сдвинуто? Может понадобиться подрузамевает худший случай, тоесть случай, когда выбирая наугад библиотекарь следовал худшей стратегии?
сколько операций перемещения (перемещается группа книг) или сколько книг будет сдвинуто?
Я так понимаю, что считать надо книги. Одна операция это перемещение одной книги с места А на место Б. Места А и Б могут быть соседними (сдвиг книги) или не (перемещение книги). Если книга лежит левее своего должного места, то её можно лишь сдвигать вправо к её месту. Напротив, если книга лежит правее своего должного места, то её можно лишь вытащить из ряда, благодаря освободившемуся вытащенной книгой месту сдвинуть некоторые книги вправо и тем самым освободить должное место вытащенной книги, дабы та могла занять его. Скажем, если имеем перестановку 5-ти книг, 43125, то можем вытащить книгу 2, сдвинуть вправо сперва книгу 1, потом книгу 3, тем самым освобождая позицию 2, куда ставим вынутую книгу 2 и получаем перестановку 42315. В результате совершили 3 операции, так как подняли с их мест 3 книги.
PP написал(а):
Может понадобиться подразумевает худший случай, тоесть случай, когда выбирая наугад, библиотекарь следовал худшей стратегии?
С учетом ответа который Вы указали, мне на ум приходит такой алгоритм, как кандидат на худший случай
Рассмотрим начальное пложение N,12,3,...,N-1 и будем ставить на место ту книгу что находится справа. Тогда
2,1 - 1,2
3,1,2 - 3,2,1 - 1,3,2 - 1,2,3
4,1,2,3 - 4,1,3,2 - 4,2,1,3 - 4,2,3,1 - 1,4,2,3 - 1,4,3,2 - 1,2,4,3 - 1,2,3,4
Количество шагов 1 = 2^1-1, 3=2^2-1, 7=2^3-1. Это мне подсказывает, что ответ который Вы приводите не о количестве операций над книгами, а о количестве операций сдвигов. ВОзможный путь к решению это по индукции показать, что такой алгоритм всегда упорядочивает за 2^(n-1)-1, а потом надо показать, что хуже быть не может. Думать неохота, но я бы перепроверил условие ибо наверняка речь идет о количестве сдвигов, а не количестве книг.
Мне как-то никогда не приходило в голову, что речь может идти о числе перестановок, получающихся в результате вытащивания и сдвигов книг. Это логично, конечно, так как практически библиотекарь книги будет сдвигать пачками вправо, а не книгу за книгой
Кстати - решение задачи Игоря на ЧессПро - (задача 937 в теме Забавные задачи и головоломки)
Пусть у нас количество монет в первой кучке - X, во второй Y и в третьей - Z. Пусть также X = Y = Z.
Делим Y на Z с остатком: Y = r*Z + z и рассмотрим двоичное представление r = rk...r1r0
Начиная с последней цифры r0 делаем следующее - если ri = 1 перекладываем монеты из второй кучки в третью, если это ноль, то из первой в третью. В конце этой процедуры во второй кучке останется z монет, а z Z и z =0. Если z 0 повторяем описанную процедуру, пока не получим ноль.
iourique на сайте ЧессПро приводит интересную задчку. Думаю, я ее решил, предлагаю местным экспертам тоже поломать голову:
На сайте Using your Head is Permitted опубликовали забавную, хотя вроде бы известную (но не мне) задачку. Как это водится, про узников и колпаки.
В тюрьме сидит 100 заключенных. В один прекрасный день им объявляют, что сегодня вечером, после того, как их разведут по их одиночным камерам, им выдадут по два колпака, белый и черный, а завтра с утра они должны будут надеть один из колпаков, после чего их выведут на плац и расставят в шеренгу в уже определенном начальником тюрьмы порядке. Если окажется, что цвета колпаков строго чередуются (б-ч-б-ч-.. или ч-б-ч-б...), их всех отпустят. Одновременно с раздачей колпаков каждому из них расскажут, в каком порядке будут расставлены все остальные, но не сообщат его место в шеренге. До заката у заключенных есть время посовещаться и выработать общую стратегию. Какой она должна быть?
