Блог пользователя Guliash

Доказать транзитивность операции
Автор Guliash, 12 лет назад, По-русски

Операция вводится на целых положительных числах. верно, если , где значит конкатенацию строковых представлений чисел x, y и последующий перевод результата в число.

Требуется доказать, что если и , то .

  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

Можно доказать, что , где a∞ — бесконечная циклическая строка, образованная строкой a. При таком определении транзитивность отношения будет очевидна.

Факт доказывается аккуратным рассмотрением, как работают оба варианта сравнения строк.

→ Ответить
»
12 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Можно доказать таким образом: Запишем три неравенства: a*10^m+b<b*10^n+a(1)

b*10^k+c<c*10^m+b(2)

a*10^k+c<c*10^n+a(3), где n,m,k длины чисел a,b,c соответственно.

Получаем:

a<b(10^n-1)/(10^m-1) (4) из (1)

b<c(10^m-1)/(10^k-1) (5) из (2)

b(10^n-1)/(10^m-1) < c(10^n-1)/(10^k-1) (6)

a<c(10^n-1)/(10^k-1) из (4) и (6). Видим что получили неравенство (3)

→ Ответить
  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    То же самое, но проще. L(x) — минимальная степень 10 большая чем x.
    A * L(B) + B < B * L(A) + A (1)
    A * (L(B) — 1) < B * (L(A) — 1) (2)
    A / (L(A) — 1) < B / (L(B) — 1) (3). Транзитивность очевидна.

    → Ответить
»
12 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Если кому-то интересно, это компаратор для решения задачи "строку разрезали на k фрагментов. Вам даны фрагменты, какая лексикографически минимальная строка могла быть изначально?"

→ Ответить