Отправлено: 03.12.18 20:42. Заголовок: Ошибка в условии?

Задача:
Для обозначения артикулов товаров в интернет-магазине используются последовательности из N символов.
Известно, что символы берутся из алфавита мощностью в 12 символов.
Петя решил сохранять в памяти артикул следующим образом – записывать подряд независимо код каждого символа артикула, используя для этого минимальное, одинаковое для кодов всех символов количество бит.
Вася решил использовать другой способ – записывать в память код каждого артикула, используя для этого минимальное, одинаковое для кодов всех артикулов количество бит.
Известно, что Вася тратит на запись кода одного артикула на 5 бит меньше, чем Петя. При каком минимальном N это возможно? В ответе укажите целое число.

Решение:

Петя:
12<2⁴
1 символ - 4 бита
на N символов 4N бит

Вася:
на каждом из N мест одна из 12 букв - всего 12^N вариантов артикула
12^N = 2^2N * 3^N < 2^2N * 4^N = 2^4N
1 артикул - 4N бит

4N < 4N на 5 бит ???
или я что-то не так делаю?

 Отправлено: 03.12.18 23:36. Заголовок: oval пишет: 4N <..

oval пишет:

цитата:

4N < 4N на 5 бит ??? или я что-то не так делаю?

Интересная задачка. Очевидно, что подход Пети когда-то даст преимущество. Поэтому предположение о некорректности условия ошибочно.
Вы взяли слишком жёсткую верхнюю оценку

цитата:

22N * 3N < 22N * 4N

На самом деле так:
1) Петя использует количество битов, равное K = ceil(log₂(12^N)), где функция ceil(x) выполняет округление вверх к ближайшему целому
2) условие ceil(log₂(12^N)) <= 4*N - 5
3) преобразуем, используя свойств логарифма:
ceil(log₂(12^N)) = ceil(N*log₂(12)) = ceil(N*(2 + log₂(3)))= 2*N + ceil(N*log₂(3))
4) сравниваем
2*N + N*ceil(log₂(3)) <= 4*N - 5
ceil(N*log₂(3)) <= 2*N - 5
или
ceil(log₂(3^N)) <= 2*N - 5
или (спасибо oval)
3^N <= 2^2*N-5
5) минимальное N, при котором выполняется это условие - N = 13.
Находится перебором (вариант - двоичным поиском).
При ручном переборе проще, конечно, этот огород не городить, а проверить N = 2, потом 10, потом 20, потом двоичный поиск.

 Отправлено: 07.12.18 12:27. Заголовок: Спасибо. Что бы не п..

Спасибо.
Что бы не пугать функцией ceil(...), задачу свела к нахождению минимального N, при котором 3^N<=2^2N-5

 Отправлено: 07.12.18 13:17. Заголовок: oval пишет: Что бы н..

oval пишет:

цитата:

Что бы не пугать функцией ceil(...), задачу свела к нахождению минимального N, при котором 3N<=22N-5

Да, это эквивалентно.