Change background image

Хорошие задачи и загадки

Тема в разделе "Разное", создана пользователем СоцБлок, 3 июн 2015.

  1. TopicStarter Overlay

    СоцБлок Старожил

    Кому как, а мне иногда нравится ломать мозг над задачами, которые просто сложные. Считаю для баланса с приколами это тоже надо. Иначе получится, что шутки быстро приедаются и все становится скучным. Считаю, что хорошая загадка подобна произведение искусства. Ею можно любоваться и повторять другим.
     
  2.  

  3. TopicStarter Overlay

    СоцБлок Старожил

    Статья взята из хабра. Надеюсь автор не против. Но над ее отгадкой мы втроем два дня бились. Это было круто!
    Задача о 64 монетах, двух заключённых и одной шахматной доске перевод

    [​IMG]

    Примечание переводчика: я заменил оригинальные обозначения сторон монеты head/tail на аверс/реверс, чтобы не вносить путаницу русскоязычными орёл/решка. На иллюстрации выше слева аверс (head), справа реверс (tail).

    Спасение невозможно?

    Это одна из тех типичных загадок о заключённых, в которых вы приговорены к смерти и можете спастись, только если докажете свои умственные способности тюремщику. Вы и ваш друг были заключены в тюрьму. Ваш тюремщик предлагает вам испытание. Если вы его выполните, вы оба будете освобождены.

    Чтобы увидеть ссылку зарегистрируйтесь ! или авторизуйтесь на Форуме !

    размещено интерактивное изображение доски. Число в нижнем левом углу отображает номер клетки в двоичной записи. Каждая цифра представляет множество, к которому клетка относится. Единица в любой позиции показывает, что клетка находится в одной половине множества, ноль — в другой. По определению каждая клетка уникальна и имеет индивидуальный набор битов.

    Чётность

    Вместо использования двух клеток как в простом примере выше мы разделим доску на различные комбинации двух множеств. Применим к этим двум регионам/множествам то же правило маркировки, что и с одиночными клетками — будем обозначать, в первом или втором регионе находится «магическая» клетка.

    Поскольку регионы являются коллекциями клеток, мы не можем просто повернуть все монеты в регионе аверсом. Вместо этого мы перевернём одну монету. Мы можем посчитать количество аверсов в регионе — если их число будет нечётным, примем это за единицу, если чётным — ноль. Переворачивание одной монеты в регионе изменит число аверсов с нечётного на чётное, и наоборот (прибавление/вычитание единицы к любому числу инвертирует его чётность/нечётность).

    Таково понятие чётности. Переключение из одного состояния в другое прибавлением или вычитанием одного бита широко используется в компьютерах.

    Чтобы изменить чётность региона, нам достаточно перевернуть одну монету в нём.

    Используя маски степеней двойки, мы можем разделить доску на регионы несколькими способами. Ниже изображены различные способы разделения доски, основанные на состоянии битов (степени двойки) в номере клетки. Совмещение этих фильтров позволяет определить одну клетку, которую можно перевернуть, чтобы изменить чётность любого/всех битов.

    [​IMG]

    20 эквивалентно логическому «И» (AND) с 000001, 21 — 000010 … 25 — 100000.

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

    Раскладка, созданная тюремщиком, имеет собственную (естественную) чётность. Монеты расположены произвольным образом, и мы можем посчитать чётность (количество аверсов) в каждом регионе. Комбинация этих битов чётности даст нам случайное шестибитное число.

    Для идентификации «магической» клетки нам необходимо как раз шесть битов, и мы можем закодировать их с помощью чётности. Мы знаем, что можем перевернуть одну любую монету, и это приведёт к изменению одного/нескольких битов числа. Всё, что нам нужно — найти нужную монету, переворачивание которой изменит комбинацию битов чётности таким образом, чтобы получилось необходимое число (двоичная запись номера «магической» клетки).

    Всё вместе

    Тут я снова отправляю читателей к интерактивной модели в

    Чтобы увидеть ссылку зарегистрируйтесь ! или авторизуйтесь на Форуме !

    .

    [​IMG]
    На левой доске можно выбрать расположение «магической» клетки. Внизу справа указан номер выбранной клетки (Target=…), слева — его двоичное представление.

    Доска справа показывает раскладку монет. Изображены только аверсы (из соображений наглядности), реверсы обозначены пустыми клетками. Кнопка «Random» заполняет доску новым случайным набором монет. Кнопка «Clear» переворачивает все монеты реверсом.

    Под правой доской серым цветом слева обозначена собственная чётность доски, зелёным справа — номер монеты, которую надо перевернуть. Слева под собственной чётностью это же число записано в двоичном виде.

    Откуда эти значения?

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

    Серое число под правой доской показывает собственную чётность доски. Для каждого фильтра мы находим, чётное или нечётное число аверсов расположено в этом регионе. Единица в любом разряде числа говорит о том, что в этом регионе нечётное число аверсов.

    Зелёное число показывает номер той клетки, состояние которой нужно изменить (перевернуть монету), чтобы чётность доски соответствовала желаемому номеру «магической» клетки. Оно вычисляется выполнением битовой операции исключающее «ИЛИ» (XOR) над собственной чётностью доски и желаемым значением.

    Исключающее «ИЛИ»

    Оператор XOR широко используется в программировании. У него несколько интересных свойств. Если исключающее «ИЛИ» применить дважды с одним и тем же значением, он вернёт исходное состояние:

    (A XOR B) XOR B = A

    Также, если мы применим XOR к какому-либо числу и полному набору битов (числу, состоящему из одних единиц), все биты исходного числа будут инвертированы. Применение XOR к числу и какому-то набору (установленных) битов инвертирует в исходном числе эти биты и сохраняет состояние остальных.

    Именно поэтому мы использовали оператор XOR для вычисления положения монеты. Для каждого бита чётности, независимо от того, содержит он уже верное значение, и мы хотим его сохранить (XOR c 0), или мы хотим переключить его (XOR c 1).

    Пример:
    Если номер «магической» клетки 101001 (41) и собственная чётность доски 010101, то нам нужно перевернуть монету в клетке 111100 (60):
    [​IMG]
    Также вы можете использовать XOR, чтобы быстро посчитать собственную чётность доски. Для этого нужно один раз обойти всю доску и провести эту операцию над каждым значением (порядковым номером) клетки с аверсом.

    Математика может спасти вам жизнь!
     
  4. TopicStarter Overlay

    СоцБлок Старожил

    How to escape a monster
    It’s getting close to Halloween, here’s a monster puzzle:

    Imagine you are sitting in a rowing boat in the middle of circular lake. Standing on the edge of the lake is a hungry monster. The monster wants to eat you. You want to escape.

    You know that, if you can reach land, you can outrun the monster, but first of all, you need to row to shore. Here’s the issue: whilst you can outrun the monster on foot, he can run faster than you can row the boat. Much faster. The monster can run four times faster than you can row. He’s also a clever monster and will always do that smartest thing to attempt to catch you; moving around the shoreline, as needed, to maximize his advantage. If he touches you, you’re dead!

    Can you escape?

    [​IMG]
    Impossible?
    I have to admit, when I first heard this puzzle, my initial thought was that it is impossible to escape. Let's imagine you made a direct dash for the shore directly opposite where the monster is currently standing.

    The radius of the lake is R. The speed you can row is v.

    The distance to the shore is simply the radius, so the time taken to get to shore is R/v.

    The monster, seeing you are making a dash for the shore, will sprint around the edge of the lake. It does not matter which direction he runs, and he will end up running half the circumference. The distance he will run is πR, and running at speed 4v, he will get to your landing point after just πR/4v. As we know that π is less than four, we can see that the monster will get there first. He’s going to eat your brains if you use this strategy!

    Towards the middle or end of your dash, once you realize the monster is closing, even if you adjust your strategy to add some tangential component, you're screwed. The faster speed of the monster means he can always catch you.

    We need a better strategy …

    [​IMG]
    Smarter Strategy
    Rowing in straight line is clearly the correct strategy (if you rowed on a curved line, you'd end up at a location that you could have gotten to quicker with a straight shot). However, we've shown that starting at the center results in failure.

    To solve this puzzle, what we first need to do is calculate the position from which a radial sprint to the shore will result in victory (we'll worry about how to get into this position in step two).



    [​IMG]


    There's an annulus (ring) at the edge of the lake in which, if we start inside, and sprint directly towards the shore we be sure of escape. Taken to the limit, in the diagram above, we can see that if we start with the monster diametrically opposed to us there is a maximum value for d.

    We know that the monster needs to run half the circumference of the lake, and the time this will take him is πR/4v. In this same time, we must row the distance d. At the limit, the time taken to complete these distances will be the same, so πR/4v = d/v, so we can calculate the maximum value of d = πR/4. If we start any closer to the center of the lake than this point, the monster will catch and eat us.

    Using a calculator we can find out that d = 0.7854R

    Getting to the escape point
    Now all we have to do is work out how to get to this escape point (on the edge of this annulus with the monster opposite us).

    When we are close to the center of the lake, we can row in tight circles. If the circle is small enough (less than a quarter of the radius of the lake), we travel radially around the lake faster than the monster can. We can use this to position ourselves relative to the monster at any arbitrary location (In this case, 180°).

    [​IMG]
    Starting from the middle, we can row in a spiral, slowly increasing our radius and, providing we stay at at radius r < R/4, we can always move faster than the monster and thus be able to make sure we position ourselves at 180° away from him.

    Once we have manoeuvred ourselves to a position d away from the edge, with the monster opposite, we can use the escape plan described above to escape.

    We know that d = 0.7854R, so this corresponds to a radius of r = (R - d), which gives a value r = 0.2146R

    This is great news because we know we can stay ahead of the the monster until a radius of r = 0.25R (travelling a quarter as slow allows us to navigate circles up to a quarter the circumference of the lake).

    So now we have our solution: We can spiral out until we reach a radius of 0.2146R < r < 0.25R with the monster opposite us, and be sure of an escape! Hurrah for math!

    What about a faster monster?
    [​IMG]
    A faster monster

    We've shown that we can outsmart a monster that can run four times as fast as we can row. The inequality above, however, shows that we have some headroom.

    What is the fastest monster we can escape?

    To calculate this, we need a little more math* …

    The fastest monster we can escape is determined when the monster arrives at the shore at exactly the same time we do. Let's define the ratio of our two speeds by the letter K. (The monster runs K-times faster than we can row). What is the maximum value for K?

    *Actually, quite a lot more math!

    Hold on, here comes the math …
    The first part of the puzzle stays the same. We know that, in a tight circle, we can row with a higher angular velocity than the monster can run. If we are inside this circle we can position the monster to any arbitrary angular position relative to us. (In fact, if we adopt an optimal strategy, and move outwards at full speed, always keeping the monster co-linear with the center of the lake, the path we follow is a semi-circle of radius R/2K).

    The radius of this circle of safety is determined by the ratio of the two speeds. It’s radius isR/K. The monster is a smart monster (as well as being hungry, he has an advanced degree in mathematics from Monster’s University), so he knows that, once you cross outside thecircle of safety he has a higher angular velocity, so as soon as he sees you leave the circle, he sprints at full speed to your side of the lake. (It’s obvious he needs to do this, if not, he’s giving you the advantage of being able to get further away!)

    [​IMG]
    [​IMG]
    Similarly, once the monster has committed to the direction he’s going to run around the lake, it would be foolish for him to change direction. If he did, he’d re-pass the point he was previously at, but now you’d be closer to the shore!

    We already know that you should always row in a straight line (anything else just wastes time), and that the monster is committed to his run. The question is: should we simply dash for the shore (as in the simple solution above), or can we gain advantage at aiming at little further around the shore?

    Sure, the straight shot to the shore is the shortest distance, but is it possible to row a slightly longer (straight) route to the shore if it would require the monster to run further to catch you? As long as the extra time it takes you to row this extra distance is less than it would take the monster to run to the same point, you are better doing it.

    In the diagram below, I've plotted out a couple of possible paths. Path #1 is the strategy from our simple solution. It is the shortest distance from the edge of the safety circle to the shore. Can we do better?

    Path #2 is a example of a generic path from the circle of safety to the shore. Yes, it's longer, but the monster also has to run longer. As the monster is committed to its run, it needs to continue around the edge of the lake to you.

    At the limit is Path #3, which is a tangent to the circle of safety. Anything past this, like Path #4 takes us back inside the circle of safety and would result in new solution being required when we exited the other side (and you'd essentially have to start the process again, otherwise, if you didn't, as soon as you went inside the circle, if you did not manoeuvre the monster opposite you again before starting your dash to shore, you would give him an advantage). The solution can not occur 'West' of Path #3 (if we define 'North' as vertically upwards).

    We can, therefore, reject Path #4, and the solution must lay somewhere between Path #1 and Path #3 inclusive.

    [​IMG]


    Note: It should be very obvious that the optimal solution does not occur 'South' of Path #1. Anything below Path #1 takes you towards the monster !!!

    More math …
    OK, we're now going to break out some trigonometry. If you're squeamish about math, you're going to want to skip to the answer section. It's only going to get worse from this point onwards …



    [​IMG]


    The distance we row from the exit point of the circle of safety to the shore, we'll call d. This value can be calculated using Pythagoras and the right hand triangle colored in the image above.
     
  5. TopicStarter Overlay

    СоцБлок Старожил

    [​IMG]

    Expanding this out we get this:

    [​IMG]
    Do you remember your trig equalities? Here's one we will be using a lot today: sin2 + cos2 = 1

    Using this equality we can simplify the equation to this:

    [​IMG]
    In the diagram on the right we can see that the monster has to run the blue route, which goes past halfway, and continues along to the interception point. The distance the monster needs to run we'll call m :

    [​IMG]

    (We are using radians for the angles)

    The puzzle reduces down to the following questions:

    • For a given speed ratio, K, what is the optimal angle Φ?

    • What is the maximum possible value for K?
    [​IMG]
    For you to escape, the time taken to row distance d, needs to be less than, or equal to the time it takes the monster to run m.

    [​IMG]
    The limit will be reached when both you and the monster arrive at the same point at the same time.

    [​IMG]
    If you both arrive at the same time, and you rowed a distance of d, the monster, who runs K times faster will have run K times the distance. The equation on the left is another way to describe the value d.

    Squaring this, we can equate it to the representation of d2 derived by Pythagoras.

    [​IMG]
    To simplify, first we multiply both sides by (K/R)2 … bear with me, you'll see why …

    [​IMG]
    This can be simplified to:

    [​IMG]

    Adding, and subtracting cos2 from the left side allows the terms to be simplified into a square expression:

    [​IMG]
    Then, using the trig equality again in the form: 1 - sin2 = cos2 gets us to here:

    [​IMG]

    Finally, rearranging we get our first important result:

    [​IMG]

    This is awesome. It gives us the relationship between K and Φ
     
  6. Svarog Легендарный Почетный форумчанин

    Я по казахски не розумию
     
  7. TopicStarter Overlay

    СоцБлок Старожил

    Summary
    [​IMG]
    If you ever find yourself in the middle of a circular lake with monster who can run less than 4.6033388489 times as fast as you can row, then row outwards and around on a semi-circular path of radius R/2K until you reach a radius of R/K, then continue straight on until you reach the shore, and escape. The path you will follow will resemble a letter 'J'.

    The original author of this puzzle, I believe, is none other than Martin Gardner. If you like this puzzle, you might like some

    Чтобы увидеть ссылку зарегистрируйтесь ! или авторизуйтесь на Форуме !

    .

    Перевод примерно такой: если вы когда-нибудь обнаружите себя посередине озера с монстром , который может бежать со скоростью не быстрее чем 4.6033388489 раза, чем можете плыть вы, то гребите наружу по полу-круговой траектории радиуса R / 2K, пока вы не достигнете радиус R / K, а затем продолжить прямо, пока не дойдете до берега, и бежать. Путь, по которому вы будете следовать будет напоминать букву «J».
     
  8. TopicStarter Overlay

    СоцБлок Старожил

    Epic fail. У меня картинки блокируется на прокси. Я не вижу то что выложил
     
  9. Svarog Легендарный Почетный форумчанин

    От стекломоя выпитого такое бывает иногда))):D
     
  10. TopicStarter Overlay

    СоцБлок Старожил

    да, в таких случаях надо нащупать
     
    Svarog нравится это.
  11. Svarog Легендарный Почетный форумчанин

    3-Д экран нужен))))
     
  12. Лакомка Активист

    Тут иногда и по русски читаешь загадки и не поймешь ничего. А если читать на английском, то вообще запаришься. Ведь у нас мозги в другую сторону направлены. Мы больше практически ум свой применяем. Дан кран без смесителя. Надо рещить задачу, как из двух кранов получать теплую воду. Это мы сразу решим. кран.jpg
     
    Svarog, Иванов, Сталин и ещё 1-му нравится это.
  13. Может попроще что-то, для затравки?
    [​IMG]
     
    Маузер К-96 нравится это.

Поделиться этой страницей