Две занимательных задачи из собеседования


Задачи, которые предлагают решить кандидатам в трейдеры во время интервью при собеседовании

Рассказывают, что кандидатам в трейдеры Лондонского инвестиционного банка (Investment Bank in London), чтобы проверить гибкость и нестандартность их мышления, предлагают решить логические и математические задачи.

Предлагаю вашему вниманию две из них. Попробуйте их решить не заглядывая в ответы, которые опубликованы ниже.

Итак…

Задача 1. 

Имеется 100 лампочек, расположенные в ряд, которые пронумерованы от 1 до 100. Каждая лампочка включается и выключается только нажатием на связанный с ней переключатель. Все лампочки вначале выключены. Затем прибывают 100 трейдеров. Первый трейдер нажимает на переключатель каждой лампочки от 1 до 100. Теперь все они включены. Второй трейдер нажимает на переключатели каждой второй лампочки, поэтому выключает лампочки под номерами 2, 4, 6, 8 и т.д. до 100, поскольку все они были включены предыдущим трейдером. Третий трейдер нажимает на переключатели каждой третьей лампочки — 3, 6, 9, 12 и т.д. Четвертый — на переключатели каждой четвертой, пятый — каждой пятой ии так далее, до тех пор, пока 100-й трейдер не нажмет переключатель 100-й лампочки.

Вопрос: Сколько лампочек будет гореть в конце и будет ли среди них лампа под номером 64?

Задача 2.

Имеется 12 монет, одна из которых фальшивая, и рычажные весы. Фальшивая монета отличается от подлинной тем, что имеет отличный от нее вес (неизвестно, тяжелее или легче). На чаши весов можно класть любое количество монет. 

Вопрос: Какое минимальное количество взвешиваний нужно произвести, чтобы определить, какая из 12 монет фальшивая?


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


РЕШЕНИЯ:

Задача 1.

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

Правильный способ — это взять случайную лампочку и посмотреть, что с ней произойдет. Давайте возьмем лампочку №12. Будет ли она включена в конце? Первый трейдер включит её, затем второй трейдер отключит (так как он нажимает все вторые переключатели (2-й, 4-й, …, 10-й, 12-й и т.д.). Затем третий снова включит её, поскольку нажимает каждые третьи переключатели (3, 6, 9, 12 и т.д.). Если мы продолжим, то увидим, что нажмут на переключатель 12-й лампы 1-й, 2-й, 3-й, 4-й, 6-й и 12-й трейдеры. Итого: включено, выключено, включено, выключено, включено и выключено. 12-я лампочка не горит.

Но, мы не будем так проверять каждую лампочку. Просто очевидно, что N-я лампочка выключена, если число переключений четное (комбинация вкл/выкл). И наоборот, он включается, если число переключений нечетно. А, поскольку количество переключений — это количество делителей порядкового номера лампочки (почему это так, подумайте сами, хотя это и очевидно, исходя из условий задачи), то вопрос в задаче можно перефразировать следующим образом: Сколько чисел от 1 до 100 будут с нечетным числом делителей? 

Как известно, единственными числами с нечетным числом делителей являются квадратные числа. Между 1 и 100, существует всего 10 квадратных чисел, так как 1=1² и 100=10², поэтому все квадраты от 1 до 100 — это 1², 2², 3², 4², … , 10². Поскольку число 64 — это 8², то лампа под номером 64 будет включена.

Задача решена!

Для тех, кто не доверяет найденному решению и хочет проверить методом перебора, есть онлайн-симулятор этой задачи.

Задача 2.

Многие правильно начинают решение этой задачи, разделив монеты на кучки и начав групповые взвешивания, чтобы минимизировать их количество. Сначала делят на 2 кучки , чтобы определить в какой из них находится фальшивая монета. Но, проблема в том, что нам неизвестно, какой вес у фальшивой монеты — она тяжелее или легче настоящей? Поэтому, если равновесие рычажных весов нарушено, мы не можем знать на какой чаше весов находится фальшивая монета — на той, что опустилась (тяжелее) или той, что поднялась (легче).

А теперь внимание: правильное решение! Монеты надо разделить на 3 равных кучки (по 4 монеты в каждой). Тогда при первом взвешивании (1-я и 2-я кучка) может быть 2 варианта:

  1. Весы в равновесии. Следовательно, фальшивая монета в 3-й кучке. Далее всё просто!
  2. Весы неравновесны. Фальшивая монета либо в 1-й, либо во 2-й кучке. Тут немного сложнее.

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

Алгоритм взвешиваний:

Обозначим все монеты от m1 до m12.
Взвешивания пронумеруем. Варианты исхода взвешивания (равновесие или больше/меньше) в каждом взвешивании — также пронумеруем. Тогда каждое взвешивание будет иметь индекс N.M.,
где N — номер взвешивания по порядку, M — возможный вариант исхода взвешивания (= — равновесие чаш весов, < — правая чаша перевесила, < — левая чаша перевесила).

Первое взвешивание (весы в равновесии)

1.1. m1+m2+m3+m4 = m5+m6+m7+m8

Второе взвешивание (весы в равновесии)

2.1. m1+m2+m3 = m9+m10+m11

Ответ: m12

Второе взвешивание (левая чаша тяжелее)

2.2. m1+m2+m3 > m9+m10+m11

Третье взвешивание

3.1. m9 = m10

Ответ: m11

3.2. m9 > m10

Ответ: m10

3.3. m9 < m10

Ответ: m9

Второе взвешивание (правая чаша тяжелее)

2.3. m1+m2+m3 < m9+ m10+ m11

Третье взвешивание

3.1. m9 = m10

Ответ: m11

3.2. m9 < m10

Ответ: m10

3.3. m9 > m10

Ответ: m9

Первое взвешивание (левая чаша тяжелее)

1.2. m1+m2+m3+ m4 > m5+m6+ m7+ m8

Второе взвешивание (весы в равновесии)

2.1. m1+m2+m5 = m3+ m4+ m6

Третье взвешивание

3.1. m1 = m7

Ответ: m8

3.2. m1 > m7

Ответ: m7

Второе взвешивание (левая чаша тяжелее)

2.2. m1+m2+m5 > m3+ m4+ m6

3 взвешивание3.1. m1 = m2

Ответ: m6

3.2. m1 > m2

Ответ: m1

3.3. m1 < m2

Ответ: m2

Второе взвешивание (правая чаша тяжелее)

2.3. m1+m2+m5 < m3+ m4+ m6

3 взвешивание

3.1. m3 = m4

Ответ: m5

3.2. m3 > m4

Ответ: m3

3.3. m3 < m4

Ответ: m4

Первое взвешивание (правая чаша тяжелее)

1.3. m1+m2+m3+ m4 < m5+m6+ m7+ m8

Второе взвешивание (весы в равновесии)

2.1. m1+m2+m5 = m3+ m4+ m6

3 взвешивание

3.1. m1 = m7

Ответ: m8

3.2. m1 < m7

Ответ: m7

Второе взвешивание (правая чаша тяжелее)

2.2. m1+m2+m5 < m3+ m4+ m6

3 взвешивание

3.1. m1 = m2

Ответ: m6

3.2. m1 < m2

Ответ: m1

3.3. m1 > m2

Ответ: m2

Второе взвешивание (левая чаша тяжелее)

2.3. m1+m2+m5 > m3+ m4+ m6

3 взвешивание

3.1. m3 = m4

Ответ: m5

3.2. m3 < m4

Ответ: m3

3.3. m3 > m4

Ответ: m4

Задача решена! Более того, мы не только определили фальшивую монету, но и узнали легче или тяжелее она настоящей. 


Комментарии 3


Чтобы читать и оставлять комментарии вам необходимо зарегистрироваться и авторизоваться на сайте.

Моя страницаНастройкиВыход
Отмена Подтверждаю
100%
Отмена Подтверждаю
Отмена Подтверждаю