Комбинаторная задачка про NUM-клавиатуру

← →
БарЛог © (2014-08-12 15:23) [0]

Всем привет.
Недавно смотрел какой-то очередной фильм про "хакеров", и придумал задачку (наверняка не я первый), но имхо, будет интересно. Вот есть на двери (допустим, сейфа) цифровая клавиатура:
(123)
(456)
(789)
(0)

При внимательном рассмотрении кнопок, вы обнаруживаете, что 4 из них "потёрты" больше, чем остальные. Соответственно, в фильмах про всяких хакеров, далее легко и просто вычисляется четырёхзначный пин-код сейфа.
Плохо помню институтскую комбинаторику, но, вроде бы число вариантов при таком раскладе (4 верно угаданные "потёртые" разные цифры из 10 кнопок) должно быть небольшим.

В общем, два вопроса:
- вычислить число вариантов для 4-х разных (не повторяющихся) цифр в пинкоде

- вычислить число вариантов, для пинкода, если две цифры в нем одинаковые (то есть, например, пин-код - 1231, и наш хакер увидел затёртые цифры 1,2,3).

Я на вскидку даже не могу предположить, какой из вариантов "выгоднее" владельцу сейфа. Но моя математика закончилась вместе с институтом.

Спасибо заранее :)

← →
БарЛог © (2014-08-12 15:27) [1]

На всякий случай еще раз и проще :)
Два случая.
В обоих случаях пин-код состоит из четырёх цифр.

Первый:
хакер подходит к двери и видит 4 затёртых цифры

Второй:
хакер подходит к двери и видит 3 затёртых цифры (значит, в пине - пара одинаковых, но необязательно идущих подряд цифр)

← →
Rouse_ © (2014-08-12 15:43) [2]

А че там комбинаторить то?
Из 4 цифр всего 24 варианта, из трех 12, из двух 6, из одной - всего один :)

← →
Rouse_ © (2014-08-12 15:48) [3]

ну и если продолжать, из 5 - 120, а из 6 - 720 ну и т.п. :)

← →
Труп Васи Доброго © (2014-08-12 15:52) [4]

Сдаётся мне, что это в идеальном случае (когда кнопки не затёрты) это размещение n!/(n-k)!, когда затёрты 4 кнопки это перестановка, равна k!, при затёртых 3х кнопках это размещение с повторениями и равно n^k.
То есть в случае одинаковых кнопок (4 цифры) получаем 10!/6!=3628800/720=5040 вариантов
При затёртых 4 кнопках будет 4!= 24 варианта.
При затёртых трёх кнопках 4^3= 64 варианта.

← →
Rouse_ © (2014-08-12 15:56) [5]

> При затёртых трёх кнопках 4^3= 64 варианта.

Неа, кнопки к примеру 123 из которых единица повторяется 2 раза, результат будет:

1123 1132 1213 1231 1312 1321 2113 2131 2311 3112 3121 3211

← →
Труп Васи Доброго © (2014-08-12 15:57) [6]

Хотя из третьего варианта надо выбросить комбинации с тремя повторениями типа 1112, 1113, 1114 и т.п. и с двойными повторениями 1122, 1133 и т.п.

← →
antonn © (2014-08-12 15:57) [7]

> из трех 12

3 кнопки, но 4 символа в пароле же

← →
junglecat (2014-08-12 15:58) [8]

1) 4! = 24
2) 4!/2 = 12

← →
Rouse_ © (2014-08-12 15:58) [9]

а вот если две кнопки то зависит от того сколько раз каждая из них повторяется, если каждая по 2 раза то результат:

1122 1212 1221 2112 2121 2211

а если одна три раза а вторая один, то:

1112 1121 1211 2111

← →
Rouse_ © (2014-08-12 15:59) [10]

> 3 кнопки, но 4 символа в пароле же

ну да.

← →
Труп Васи Доброго © (2014-08-12 16:01) [11]

Ну да, перепутал n и к. Не 4^3, а 3^4

← →
Rouse_ © (2014-08-12 16:07) [12]

А кстати с тремя кнопками получается 36 вариантов а не 12, ибо не ясно сколько раз какая цифра повторяется :)
Тогда и с двумя кнопками получается 10 вариантов, по этой-же причине.
Ну а с четырьмя как и было - 24 комбинации.
Вывод - из трех цифер лучше :)

← →
Inovet © (2014-08-12 16:19) [13]

Надо смотреть на степень истёртость кнопок - более истёртые повторяются больше раз. Последовательность нажатий надо сотреть по направлению истёртостей по движению пальца от предыдущей цифры. Первая цифра будет истёрта в средине. А вы тут перестановки, комбинаторы, панимаешь.

← →
Труп Васи Доброго © (2014-08-12 16:28) [14]

> А кстати с тремя кнопками получается 36 вариантов а не 12

Я же написал формулу n^k вариантов n - число возможных цифр (в данном случае 3), k - число цифр в коде. Вот и получается 3^4= 81 вариант. Но, так как не может быть более двух повторений в одном наборе, то количество вариантов уменьшается. Выбрасываем тройные+ повторы и двойные дубли. Тройных+ повторов будет 9*3= 27 и двойных дублей 15 штук. То есть выкидываем 27+15=42 варианта. Имеем 81-42= 39 возможных вариантов.

← →
junglecat (2014-08-12 16:30) [15]

> Последовательность нажатий надо сотреть по направлению истёртостей
> по движению пальца от предыдущей цифры

а может, я сразу четырьмя нажимаю)

← →
Rouse_ © (2014-08-12 16:38) [16]

> Имеем 81-42= 39 возможных вариантов.

У меня чей-то еще 3 варианта дополнительных никак не получаются :)

← →
Труп Васи Доброго © (2014-08-12 16:47) [17]

> У меня чей-то еще 3 варианта дополнительных никак не получаются
> :)

Ладно, не рубите в математике, давай по программистски посчитаем.
У нас для записи четырёхзначного числа используется всего три цифры (пусть это будет 123) То есть имеем троичную систему счисления.
Есть четырёхзначное число в троичной системе счисления. хххх
Как посчитать максимальное число, которое можно закодировать таким способом? Правильно 3333 (в троичной системе)
расписываем степени над позициями числа 3210 и получаем 3^3+3^2+3^1+3^0= 27+9+3+1= 39
Так понятнее, программисты?

← →
Труп Васи Доброго © (2014-08-12 16:50) [18]

Один вариант (нулевой) я уже выкинул.

← →
MBo © (2014-08-12 16:55) [19]

для трёх - 4! * 3 / 2!=36
Смысл -
24 комбинации из 4-х разных цифр, в каждой можно заменить любую из трёх цифр - отсюда 72 варианта. Но половина лишняя, т.к. это перестановки одной цифры.

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

> Труп Васи Доброго © (12.08.14 16:47) [17]
> Ладно, не рубите в математике, давай по программистски посчитаем.

Да рубим, в принципе, но давай по программистки :)
На тебе 36 вариантов для трех цифр (12 + 12 + 12), добавь три недостающих комбинации:

1123 1132 1213 1231 1312 1321 2113 2131 2311 3112 3121 3211 1223 1232 1322 2123 2132 2213 2231 2312 2321 3122 3212 3221 1233 1323 1332 2133 2313 2331 3123 3132 3213 3231 3312 3321

и то-же самое для двух цифр (14 вариантов 6 + 4 + 4):

1122 1212 1221 2112 2121 2211 1112 1121 1211 2111 1222 2122 2212 2221

> 3^3+3^2+3^1+3^0= 27+9+3+1= 39

Да, кстате, для тех кто щарит в математике, нужно знать, что сумма вот этих четырех цифирь "27+9+3+1" равна сорока :)))
(ну это я уже в оффтоп ушел, пардон )))

X5^2 = X*(X+1)|25

> БарЛог © (12.08.14 15:23)
>
> Всем привет.
> Недавно смотрел какой-то очередной фильм про "хакеров",
> и придумал задачку (наверняка не я первый), но имхо, будет
> интересно. Вот есть на двери (допустим, сейфа) цифровая
> клавиатура:
> (123)
> (456)
> (789)
> (0)
>
> При внимательном рассмотрении кнопок, вы обнаруживаете,
> что 4 из них "потёрты" больше, чем остальные.

Не путай сейф с "домофоном". :)

> Да, кстате, для тех кто щарит в математике, нужно знать,
> что сумма вот этих четырех цифирь "27+9+3+1" равна сорока

Тля! Во я умный после самогона становлюсь! И никто не поправил, что я считаю через назад.
Формула изначальная правильная, всего вариантов 3^4=81. И если через троичную систему тоже получается число 2222 = 2*3^3+2*3^2+2*3^1+2*3^0=80 плюс вариант 0000, итого 81 вариант.
Дублей будет по той же формуле 2^4=16 с каждой парой цифр 1:2, 1:3 и 2:3 то есть 48 вариантов. Убираем повторяющиеся в этих наборах "повторы" 1111, 2222 и 3333 (в паре 1:3 есть вариант 1111 и 3333, поэтому их дубли в парах 1:2 и 2:3 убираем, то-же для дубля 2222 в парах 1:2 и 2:3) Итого нужно исключить 48-3=45 комбинаций из одной и двух цифр. К вящей радости Розыча получаем правильное число вариантов 81-45=36.
Посыпаю голову пеплом, я прошлый раз забыл исключить 3 повтора "повторов" 1111, 2222 и 3333, поэтому и получалось 39, вместо 36. Каюсь, готов искупить вину вкуснейшим медовым самогоном. Так что, будете у нам в Урюпинске - милости просим.

> К вящей радости Розыча получаем правильное число вариантов
> 81-45=36.

Да я сам вчера раза 4 считал никак допереть не мог как у тебя так вышло :)

← →
Дмитрий Белькевич (2014-08-19 01:56) [27]

Я бы, например, 43211234 поставил. Пусть ломают.

p.s. почему код из 4х цифр должен быть 4х значным? :)

Комбинаторная задачка про NUM-клавиатуру Найти похожие ветки