понедельник, 9 января 2012 г.

Задачки на сообразительность - 10

Первая рабочая неделя после новогодних праздников не всегда дает время для "раскачивания". 

Один из способов настроиться на рабочий лад - решить несколько задачек ;). 



ЗАШИФРОВАННОЕ ЧИСЛО

Необходимо назвать Число удовлетворяющее следующим правилам:
1) Число содержит 10 цифр (например 1023456789)
2) Число само себя описывает|зашифровывает:
- первая цифра это число нулей в Числе
- вторая цифра это число единиц в Числе
...
- десятая цифра это число девяток в Числе
т.е. если в Числе 5 нулей и 3 двойки то Число будет выглядеть как 5x3xxxxxxx (где x - какие нибудь цифры)

Вопрос: Назовите это число
КОДИРУЮ ЗА ЗОЛОТО

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

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

Вопрос: Объясните как менеджер разрезал золото и как выплачивалась оплата каждый день.

КОТ И МЫШЬ

Кота Леопольда таки достала мышь.Он смог ее загнать в норку. Но вот незадача в норке 5 выходов. Все выходы последовательны (т.е. мышь может из первого выхода перебежать во вторую; из второй - в первую или третью, из третьей в четвертую или во вторую). 

Мышь можно поймать засунув лапу в один из выходов (засунуть лапы сразу в два выхода нельзя).

После каждой попытки кота (сунул - высунул) мышь перебегает к другому выходу. Логика мыши не подчиняется логике - либо вправо либо влево.

Мышь не пытается выскочить из норы.

Вопрос: Какую стратегию (первый вход, последний вход, пятый, опять первый ....)  вы можете предложить, чтобы поймать мышь как можно скорее?

23 комментария:

  1. 1. 6210001000

    Ясно, что нулей ближе к концу будет много.
    Поэтому на первом месте стоит какое-то большое X, а на соответствующем этому X месте - 1. Единичка не может входить ровно 1 раз, значит на втором месте Y>=2. Значит, на месте Y стоит ещё одна 1, а Y=2. 4 места заняли, значит нулей X=6.

    2. Два разреза на три доли 1/7,2/7,4/7. Степени двойки - наше всё. Ими набрать можно любую долю от 1 до 7, но со сдачей! Это значит, что до конца недели программисту нельзя покупать пельмени :(

    ОтветитьУдалить
  2. Ответы писать можно?
    1. Беловежская пуща
    2. 9000000000
    3.
    4.

    ОтветитьУдалить
  3. Сильно не уверен, но придумалось такое решение про золото:
    http://goo.gl/bfZBI

    ОтветитьУдалить
  4. Пока ограничил вывод комментариев. Слишком много правильных ответов )))) - даем занятым подумать до пятницы. В пятницу все комментарии будут показаны.

    ОтветитьУдалить
  5. >Василь
    Про золото интересно, но все решается гораздо легче ;)

    ОтветитьУдалить
  6. Моя версия решения задачки про золото:D
    Первое движение-круг(обрезающий углы):делит на 5 частей.
    Второе: например, из верхнего левого угла в середину правой стенки(грани):итого 7 кусков.
    Леша, 6 класс :D
    http://vkontakte.ru/alexsey_lobanovskiy

    ОтветитьУдалить
  7. Леша: картинка
    http://postimage.org/image/52v40gnwn/
    (пока не знаю, как правильно делать ссылки на картинки)

    ОтветитьУдалить
  8. Ответы
    1. И ответ на этот вопрос знает Google!
      Вопрос не в геометрии, а в хитрости ;)

      Удалить
    2. Я бы советовал дать подсказку из оригинала...
      Т.к. сложно предположить, что такое возможно в действительности :)))
      "Ответ предполагает, что работник не будет тратить золото, которое ему платят"

      Удалить
    3. Не хитрим! Я кстати решал без подсказки. Как народу сейчас задаю так и здесь воспроизвел.

      Удалить
    4. "Не хитрим!"
      :D
      Хорошо. Тогда скажите может ли тратить заработанное за день золото работник?

      Удалить
  9. 1. Беловежская Пуща - это просто
    2. 6210001000 - решил на бумаге
    3. Кусок поделен на три части 1/7, 2/7, 4/7. У менеджера глаз наметан слитки делить.
    4. Сувать лапу последовательно в каждый выход, начиная со 2-го (до 6-го) по два раза, т.к. неизвестно в каком выходе сидит мышь и куда она двинется. Т. е. за 10 попыток мышь 100% будет поймана.

    ОтветитьУдалить
  10. золотой слиток делится двумя параболами пересекающимися в одной плоскости

    ОтветитьУдалить
  11. стратегия поиска мышки - сначала деление по пополам, потом последовательная проверка каждой норки

    ОтветитьУдалить
  12. Задача с мышью не решена.

    Кошка: 22444332
    Мышь: 43212123...

    Да и условия в ней не до конца понятны. Видит ли киса мышь и наоборот? А вот норок, мне кажется, первоначально все-таки было 7 в условиях.

    ОтветитьУдалить
  13. Согласен. Мышка проскочила. Есть повод подумать над правильным ответом. Если кто решит с 7-ю будет тоже прикольно.

    ОтветитьУдалить
  14. Ох, помню, как намучился с этой задачей про мышку))

    Наиболее короткое из известных мне решений для пяти норок: 2-3-4-2-3-4

    Доказательство решения:
    Сначала сделаем предположение, что мышь находится в чётной норке (норки вопреки програмистским традициям пусть нумеруются от 1 до 5).
    Соответственно нашему предположению, мышь может находиться либо во второй, либо в четвёртой норке. Проверяем вторую норку. Если не поймали, то мышь сейчас в 3 или в 5. Проверяем 3. Если не поймали, то мышь в 4. Проверяем 4.
    Если не поймали, значит наше предположение было неверно. Значит изначально мышь была в нечётной норке.
    Заметим, что мышь перебегает только по соседним норкам, то есть каждый ход чётность норки, в которой находится мышь, меняется. Это значит, что после трёх совершённых нами ходов мышь либо поймана, либо точно в чётной норке. Повторяем ещё раз те же три хода с теми же рассуждениями. Теперь мышь точно поймана.

    Расширение решения на n норок, на самом деле, аналогичны (строго не доказывал, но, наверняка, матиндукция здесь всё разрулит) – прогоняем все норки от 2-й до n-1 дважды. Единственное отличие в том, что если n – чётно, то после первой итерации следует сделать ещё один какой-нибудь случайный ход (чтобы суммарное кол-во ходов было нечётным и мышь оказалась в чётной норке), после чего повторить итерацию.

    Получается, что данное решение гарантирует отлов мыши в n норках не более чем за 2*(n-2) + (n+1)%2 ходов. Как-то так.
    :3

    ОтветитьУдалить