300000
12468
Knot Colouring
Якщо вас тільки цікавить, як вирішити цю проблему, а не теорія, що стоїть за нею, перейдіть до «Які підказки для пошуку забарвлення методом проб і помилок?»
Про інваріанти
можуть деформуватися один в одного, не розрізаючи лінію вузла.
В іншому випадку наступна послідовність показує, як спростити діаграму Тузун-Сікори до кола.
Доказ того, що діаграма Тузун-Сікора є розв'язаним вузлом.
Прикладом інваріанта є мінімальна кількість перетинів, яке може мати будь-яка з нескінченно багатьох еквівалентних діаграм. Цей інваріант важко знайти, тому що не можна перевіряти нескінченно багато діаграм.
Але яким може бути інваріант, який можна обчислити для даної діаграми? Складно уявити, яка властивість не змінюється при деформації, коли деформувати діаграму можна будь-яким способом.
Триколірність є інваріантною.
Яка з 3 діаграм є триколірною?
N-колірність
Виникає багато питань.
Вступ до модульної арифметики
Довести всі твердження модульної арифметики можна, ввівши множник k і переформулювавши рівняння ≡ як нормальне рівняння. Для скорочення позначень використовуємо:
'ціле число' для 'цілого числа',
'pq' для 'p помножене на q',
«∃» для «Існують»,
':' для 'з власивістю', і
«A → B» для «від A слід за B».
тобто повинен існувати множник m з властивістю, що a = b + mp. Якщо коротко, то це
(a ≡ b mod N) → (∃ ціле число m: a = b + mp)
(c ≡ d mod N) → (∃ ціле число n: c = d + np)
Склавши обидва рівняння, отримаємо a + c = b + mp + d + np = b + d + (m+n)p
→ a + c ≡ (b + d) mod N
Доведіть: якщо a ≡ b mod N, то для будь-якого цілого числа m маємо ma ≡ mb mod N
Після множення з m отримуємо:
ma = мб + мкН
→ ма ≡ мб мод N
Доведіть: якщо a ≡ b mod (PQ), то a ≡ b mod P.
→ ∃ ціле число k: a = b + k(PQ)
→ a = b + (kQ)P
→ a ≡ b mod P
А як щодо протилежного напрямку?
6 ≡ 1 mod 5 але
6 ≢ 1 mod 15, тому що 6 і 1 не відрізняються кратно 15.
Чому правдоподібно, що зворотне не вірно?
У моді рівняння N обидві частини ≡ можуть мати N різних значень. У моді рівняння (NM) обидві частини ≡ можуть мати різні значення NM. Тому мод відношення (NM) несе більше інформації, ніж мод відношення N. Відкинути інформацію шляхом переходу від моду (NM) до моду N легко, але зворотне створення інформації з нічого неможливо. Грубо кажучи, в цьому сенсі нормальна рівність з використанням = еквівалентно ≡моду ∞(нескінченність).
Як побічний коментар, це відкриває можливість того, що в додатках, де розв'язок включає цілі числа і де шукають рішення у вигляді рівняння за допомогою '=' і де відомо, що існує верхня межа абсолютної величини чисел у розв'язку, тоді стратегія може полягати в тому, щоб почати з пошуку розв'язку mod N для деякого малого простого числа N, а потім обчислити мод ідентичності N^2, потім mod N^4 і так далі, поки степінь N не буде більшою за верхню межу, відому для розв'язку, і тоді можна відкинути мод і отримати точний розв'язок за допомогою = .
Такий метод, званий підйомом Хенсела, може бути використаний для розкладання одновимірних багаточленів спочатку відносно деякого малого простого числа, а потім, нарешті, точно над цілими числами.
Доведіть: a + b ≡ ((a mod N) + (b mod N)) mod N
b і b mod N відрізняються кратно N: b = (b mod N) + qN
→ a + b = (a mod N) + (b mod N) + (p + q)N
→ a + b ≡ ((a mod N) + (b mod N)) mod N
Доведіть: ab ≡ ((a mod N)(b mod N)) mod N
b і b mod N відрізняються кратно N: b = (b mod N) + qN
→ ab = ((a mod N) + pN)((b mod N) + qN)
= (a mod N)(b mod N) + [(a mod N)q + (b mod N)p + pqN]N
→ ab ≡ (a mod N)(b mod N) mod N
Доведіть: якщо P(x,y,...) є багаточленом змінних x,y,... потім P(x,y,...) ≡ P((x mod N),(y mod N),...) mod N
Доведіть: У модульній арифметиці модуль є простим числом, ділення на цілі числа дає знову цілі числа.
Почнемо з того, що для простого числа p і будь-якого цілого числа a ≢ 0 mod N обернене 1/a mod N також є цілим числом. Нам потрібно ≢ 0 mod N, тому що також в модульній арифметиці ділення на нуль неможливо.
Нехай u буде u ≡ 1/a mod N. Для u бути оберненим модом N, це означає:
ua ≡ 1 mod N
→ ∃ ціле число k: ua = 1 + kp
Це має вигляд ідентичності Безу: ua + vp = GCD(a,p), де GCD(a,p) є Найбільшим Спільним Дільником a,p і де v=-k. Оскільки p є простим числом, і a неє кратним p, тому GCD(a,p)=1.
Множники u,v в ідентичності Безу можуть бути обчислені через розширений алгоритм Евкліда, і обидва, u,v, є цілими числами.
якщо you=1/a є цілим mod N, тоді b/a = bu також є цілочисельним mod N, який мав бути показаний.
Приклад: 1/3 ≡ 5 mod 7, тому що 1 = 3(1/3) ≡ 3(5) = 15 = 2(7) + 1 ≡ 1 mod 7.Коли ma ≡ mb mod N еквівалентний a ≡ b mod N?
Китайська теорема залишку.
Це те, що стверджує китайська теорема залишку.
Якщо для двох рівнянь
x ≡a 1 mod N1
x ≡a 2 mod N2
дільники N 1,N2 є взаємно простими, тоді існує рівно одне значення для x до кратних p1p2, яке задовольняє обидва модульних рівняння.
Одним зі способів отримати розв'язок є використання розширеного алгоритму Евкліда для розв'язання ідентичності Безу m1N1+ m 2N2= 1 шляхом обчислення m1,1,m2, а потім використовувати формулу
х =a1m2N2+a2m 1M1
=a1(1 - m1N1) + a2м1N1
=a1 + (a2 - a1)m1N1
який показує x ≡ a1 mod N 1 та еквівалентно x =a2 +(a1 - a 2)m2N2, який показує x ≡ a2mod N2.
Якщо є більше двох модульних рівнянь, то можна багаторазово заміняти два з них одним, поки не отримаємо рішення у вигляді одного модульного рівняння. При кожній заміні нове число дільника зростає, стаючи добутком двох дільників об'єднаних рівнянь.
Як довести, що N-забарвлення є інваріантним?
Як можна показати, що Рейдемейстер, який я переміщую, не змінює колірність?
Якщо кольори пасом A і B, як зазначено, то умова забарвлення вимагає на лівому малюнку A + B ≡ 2B mod N і на правому малюнку B + A ≡ 2A mod N. В обох випадках B = A є рішенням:
Це означає, що виконання ходу Рейдемейстра I не змінює колірність.
Як показати, що хід Рейдемейстра II не змінює колірність?
Якщо кольори пасом A, B і C, як зазначено, то C однозначно визначається з умови B + C ≡ 2A mod N на лівому малюнку так C ≡ (2A - B mod N) і на правому малюнку A + C ≡ 2B mod N so C ≡ (2B - A mod N). Це визначає колір нового пасма при виконанні ходу Рейдемейстра II. На кольоровість це не впливає.
Як можна показати, що хід Рейдемейстра III не змінює колірність?
Якщо кольори пасом A, B, C, D, E, F та G, як зазначено, тоді трьома умовами ліворуч є:
A + D ≡ 2C mod N
E + F ≡ 2D mod N
F + B ≡ 2C mod N .
При усуненні внутрішньої нитки F умовою на зовнішніх пасмах є
2D - E ≡ 2C - B mod N, який за допомогою A + D ≡ 2C mod N спрощується до
2D - E ≡ A + D - B mod N і, таким чином, A - B - D + E ≡ 0 mod N.
3 умови праворуч:
E + G ≡ 2C mod N
G + B ≡ 2A mod N
A + D ≡ 2C mod N
При усуненні внутрішнього пасма G стан на зовнішніх пасмах такий:
2C - E ≡ 2A - B mod N, який за допомогою 2C ≡ A + D mod N спрощується до
A + D - E ≡ 2A - B mod N і, таким чином, 0 ≡ A - B - D + E mod N.
F і G обчислюються з будь-якого з відносин, в яких вони з'являються.
Робимо висновок, що для обох діаграм умови щодо кольорів зовнішніх ниток однакові: A + D ≡ 2C mod N та A - B - D + E ≡ 0 mod N.
Таким чином, або обидві діаграми мають, або жодна з них не має забарвлення, і, отже, кольоровість незмінна при ходах Рейдемейстера III.
Тривіальність, еквівалентність і незалежність забарвлення
1) При додаванні однієї і тієї ж константи, скажімо S, до кожного кольору, відмінності не змінюються:
(A+S) - (C+S) = A - C + S - S = A - C і
(C+S) - (B+S) = C - B + S - S = C - B і
тому умови все ще виконуються.
2) Ми бачили раніше як правило модульної арифметики, що ми можемо помножити обидві частини ≡ на число, взаємне просте до N і отримати еквівалентний розв'язок системи рівнянь і, таким чином, еквівалентне забарвлення.
Чи має значення мод кольорності 2?
Почнемо з пасма кольору А, яке продовжується як пасмо В після перетину під першим шляхопроводом кольору С. Тоді A, B, C пов'язані через A + B ≡ 2C mod 2 і після додавання B з обох сторін A ≡ B mod 2, тому що 2B ≡ 2C ≡ 0 mod 2. Продовжуючи це міркування на всіх перехрестях, випливає, що всі пасма мають або парний колір (0), або непарний колір (1). Це надає тривіальне забарвлення.
А як щодо моду кольорності (2N), тобто парного числа по модулю?
Як наслідок, кожен мод забарвлення (2N) є еквівалентним моду забарвлення N.
Для якої N є N-кольорність корисною, а не тривіальною?
Чи достатньо знати всі забарвлення mod P і mod Q, де P і Q є взаємно простими, щоб знати всі забарвлення mod (PQ)?
Відповідь: Так.
Доказ:
Нехай1,2 це є кольори одного пасма в забарленнях mod P і mod Q.
Тоді Китайська теорема залишку гарантує існування та унікальність одного цілого числа A mod PQ, що і задовольняє обидві умови.
A ≡a1 mod P
A ≡a2 mod Q.
Це можна повторити для кожного пасма, даючи значення кольорів A, B, C,... мод PQ.
На кожному перетині дві умови забарвлення
(A + B - 2C) mod P =a1+ b11≡ 0 mod P
(A + B - 2C) mod Q =a 2 +b2-2c 2 =0 mod Q
є задовільними. Єдине значення (A + B - 2C) mod PQ, яке дорівнює нулю mod P і нулю mod Q це A + B - 2C ≡ 0 mod PQ. Це показує, що значення кольорів A, B, C,... надає забарвлення mod PQ.
Оскільки всі натуральні числа мають просту розкладку на множники, їх можна записати як добуток степенів простих чисел. Тому можна знайти всі числа забарвлень, досліджуючи лише всі степені всіх непарних простих чисел як числа забарвлень. Раніше ми бачили, що просте число 2 і степінь 2 є не можливими числами забарвлення.
Можна було б почати перевіряти наявність розфарбовування по модулю деякого простого числа і, якщо успішно, то повторювати перевірку з все більш високими степенями цього простого числа, поки більше не існує кулінгу.
Які підказки для пошуку забарвлення методом проб і помилок?
- Щоб вирішити, яке пасмо розфарбувати далі, натисніть Enter, щоб відсортувати рівняння за їхньою кількістю літер, тобто за терміновістю.
- Якщо рівняння має кілька літер, виберіть одну, яка зустрічається в більшості інших рівнянь, щоб більше рівнянь спрощувалося, коли при присвоюється номер. Аналогічно, наведіть курсор миші на рівняння, подивіться обведений перехід і на цьому переходіі натисніть на те незабарвлене пасмо, яке має найбільше шляхопроводів.
- Літери з правого боку ≡ обчислюються швидше, ніж літери ліворуч. Щоб обчислити букву зліва, потрібно розділити на 2, що, можливо, вимагатиме додати N праворуч, щоб стати парним. Це не складно, але в умовах конкурсу час дорогоцінний. З цієї ж причини, вгадуючи значення літери, можна взяти букву ліворуч від ≡.
- Для економії часу не турбуйтеся про обчислення значень в інтервалі 0..N−1. Значення можуть бути негативними або довільно великими. Якщо вони правильні, то фіолетове рівняння стає зеленим, і це є те що важливо..
- Якщо в рівнянні залишилася лише одна буква, тоді фон буде фіолетовий, і тоді не буде вибору, значення потрібно обчислити, щоб зробити рівняння зеленим. Приклади дивіться в інструкції.
- Як показано вище в цей розділ > «Якщо у кого є одне забарвлення...» розділу, значення всіх літер можуть бути зміщені на одне і те ж постійне значення. Тому найпершій літері , яку хочеться призначити, можна дати значення 0 без втрати загальності. Ніхто не буде пробувати будь-яке інше значення для цієї літери, тому що його завжди можна змістити до нуля.
- Щоб 2-а літерамбула кольоровою, потрібно врахувати лише два випадки: 1) вона має те саме значення, що й перша буква, тобто 0, і 2) вона має інше значення. У цьому випадку потрібно лише розглянути 1, тому що ми побачили, що всі числа можна помножити на 2.. (Н-1) (де N — просте число доступних кольорів) і вони все ще мають еквівалентне рішення. Будь ласка, посилання цей розділ > «Якщо у когось одне забарвлення...». Наприклад, якщо N = 5 і можна було б спробувати інше значення для 2-ї призначеної літери, наприклад 3, і отримати рішення, то множення цього значення (і всіх інших значень) на 2 зробило б 3 до 3×2 = 6 ≡ 1 mod 5 таким чином до a 1. Тому 2-у букву потрібно спробувати лише як 0 і 1.
- Тести - це теж питання часу. Можна заощадити час, вводячи від'ємні числа, коли їх обчислюється швидше, ніж додатні. Інтерфейсу не потрібні числа в діапазоні 0..N-1.
- Коли рівняння стає червоним, то умова ≡ нe виконується, і хоча б одне число потрібно змінити. Потім спробуйте інше число. Щоб не пропустити числа, можна спробувати числа порядку 0,1,...,N-1 і зупинитися при знаходженні забарвлення.
- Під час зворотного відстеження, натиснувши кнопку скасування, якщо ви бачите фіолетове рівняння, можна знову натиснути кнопку скасування, не замислюючись. Причина в тому, що фіолетове рівняння має тільки одну літеру, і для цієї літери існує тільки одне можливе значення (mod N), тому ніякого іншого значення для цієї літери в даній ситуації пробувати не потрібно.
- Щоб систематично шукати і не упускати жодної можливості забарвлення, можна було б почати з призначення кожній змінній значення 0, яке дає тривіальне рішення, а потім почати відступати, щоб отримати нетривіальне рішення.
- Діаграми вузлів, які використовуються в цій грі, мають вже мінімальну кількість перетинів. Але якщо діаграми не будуть мінімальними, то вигідно буде спочатку їх спростити. Без вищевказаних методів прискорення довелося б спробувати забарвлення NC, де N - кількість кольорів, а C це кількість перетинів = кількісті пасом. Зменшення кількості перетинів лише на 1 знижує зусилля на КОЕФІЦІЄНТ N.
Чи є вузли, які не можна зафарбувати?
Діаграма з написом «Тузун-Сікора» у верхній частині сторінки є лише однією з нескінченно багатьох діаграм вузла і тому також не розфарбовується.
Чи існує ще більше колірних інваріантів і як їх можна обчислити?
Якщо діаграма вузлів має перетини C, то вона також має пасма C і, таким чином, система умов має матрицю коефіцієнта C×C, де кожен ряд представляє перетин і складається або з двох -1 і одного 2, або з +1 і а -1 (петльовий перетин Reidemeister I). Кожен стовпчик відповідає пасму і має стільки ж 2, скільки пасмо має шляхопроводів: або два -1, або один -1 і один +1.
Умови утворюють однорідну лінійну систему (права частина містить тільки 0) і питання полягає в тому, щоб знайти числа забарвлення по модулю, які є нетривіальними лінійними незалежними рішеннями (забарвлення).
Як і в лінійній алгебрі, матриця приводиться в діагональну форму шляхом обміну рядами і додавання кратних рядів до інших рядів. Крім того, ці кроки також виконуються колонками. Тут заборонено множити ряди та стовпці на число, оскільки це додало б кольоровий номер за модулем, який є визначником матриці і дорівнював би нулю, а це додало б додаткове забарвлення. Замість цього потрібно вибрати кілька разів 2 ненульові компоненти стовпця/ряда, скажімо, A,B, щоб використовувати розширений алгоритм Евкліда для знаходження p,q, що задовольняє pA + qB = GCD(A,B). p,q — множники двох рядів/стовпців. Після заміни рядів/стовпців GCD(A,B) стає діагональним елементом. Результатом є діагональна матриця, яка називається Нормальною формою Сміта, де зазвичай верхній лівий кут починається з 1, за якими слідують числа, які є кожним множником наступного числа в діагоналі. Останній діагональний елемент дорівнює нулю, оскільки кожна діаграма вузла дозволяє тривіальне забарвлення, використовуючи лише один колір. Тому достатньо обчислити нормальну форму Сміта після скидання будь-якого одного стовпця та будь-якого одного ряда.
Обчислення визначника матриці коефіцієнта C×C дає нуль, оскільки стовпці додають до нуля. Обчислення визначника після скидання одного рядка і одного стовпця дає одне число, яке є добутком чисел на діагоналі нормальної форми Сміта. Таким чином, нормальна форма Сміта дає більше інформації приблизно для тих самих зусиль.
Приклад: Для цієї діаграми з 83 перетинами матриця коефіцієнтів має розмір 83×83.
Нормальна форма Сміта має діагональ, що починається у верхньому лівому куті з 79 разів на 1, за якою слідують 3, 3, 85837301265 (= 3 x 5 x 5722486751), 0. Це означає, що існує три незалежних 3-забарвлення та один 85837301265-забарвлення, що означає, що він також має 5-забарвлення, 15-забарвлення, 3x5722486751-забарвлення та 5x5722486751-забарвлення.
Якщо діаграма не має забарвлення, то всі діагональні числа дорівнюють 1, крім 0 в останньому положенні.
Наступна діаграма належить вузлу 12a801.
Нормальна форма Сміта (SNF) має по діагоналі дев'ять 1, за якими слідує 3,45,0. У цій формі кожне число є множником наступного діагонального числа. А кратність забарвлення - це кількість діагональних елементів, в яких воно зустрічається як множник. Таким чином, кожна діаграма цього вузла має два незалежних 3-забарвлення і одне 45-забарвлення, що означає, що цей вузол також має одне 5-,9-,15-забарвлення.
Статистика забарвлення вузлів
https://cariboutests.com/qi/knots/colour3-15-N.txt
подає списки для кожного вузла з номером перетину ≦ 15 всіх записів Нормальної форми Сміта, які не є 0 або 1. Ці числа були обчислені з однієї діаграми, але вони інваріантні і, отже, однакові при обчисленні з будь-якої діаграми цього вузла. Якщо вам подобаються зображення кольорових вузлів, ви можете завантажити плакат з нашої колекції плакатів, натиснувши на домашню сторінку «Головна» > «Плакати», що ведуть до https://cariboutests.com/images/posters/knot_colouring_portrait.pdf
. Наскільки сильне N-забарвлення як інваріант?
Таблиця 1: Статистика інваріантів кольорів
# cr: # переходів
# kn: # вузлів
# cl1: # класів коли розглядається тільки список забарвлення простих чисел.
# cl2: # класів при розгляді тільки списку кратностей забарвлення простих .
# з cl3: # класів при розгляді списку записів нормальної форми Сміта <> 1
ABS: exp(ln(noofcl3[cr])/(cr-3))
= (cr-3)-й корінь з (# з cl3)
# з cr | # з kn | # з cl1 | kn/cl1 | # з cl2 | kn/cl2 | # з cl3 | on/cl3 | abs↑ |
---|---|---|---|---|---|---|---|---|
3 | 1 | 1 | 1.00 | 1 | 1.00 | 1 | 1.00 | |
4 | 1 | 1 | 1.00 | 1 | 1.00 | 1 | 1.00 | 1.000 |
5 | 2 | 2 | 1.00 | 2 | 1.00 | 2 | 1.00 | 1.414 |
6 | 3 | 3 | 1.00 | 3 | 1.00 | 3 | 1.00 | 1.442 |
7 | 7 | 7 | 1.00 | 7 | 1.00 | 7 | 1.00 | 1.627 |
8 | 21 | 13 | 1.62 | 14 | 1.50 | 16 | 1.31 | 1.741 |
9 | 49 | 25 | 1.96 | 29 | 1.69 | 33 | 1.48 | 1.791 |
10 | 165 | 47 | 3.51 | 53 | 3.11 | 62 | 2.66 | 1.803 |
11 | 552 | 81 | 6.81 | 93 | 5.94 | 116 | 4.76 | 1.812 |
12 | 2176 | 136 | 16.00 | 162 | 13.43 | 203 | 10.72 | 1.805 |
13 | 9988 | 234 | 42.68 | 271 | 36.86 | 342 | 29.20 | 1.792 |
14 | 46972 | 409 | 114.85 | 488 | 96.25 | 623 | 75.40 | 1.795 |
15 | 253293 | 722 | 350.82 | 855 | 296.25 | 1100 | 230.27 | 1.792 |
Як найбільше число забарвлення вузлів із перетинами C залежить від C?
Таблиця 2: Таблиця B(C) = Nmax1/(C−1)
C | Nmax | вузол | BС) |
---|---|---|---|
3 | 3 | 31 | 1.732 |
4 | 5 | 41 | 1.710 |
5 | 7 | 52 | 1.627 |
6 | 13 | 63 | 1.670 |
7 | 19 | 76 | 1.634 |
8 | 37 | 817 | 1.675 |
9 | 61 | 933 | 1.672 |
10 | 109 | 10115 | 1.684 |
11 | 199 | 11a301 | 1.698 |
12 | 353 | 12a1188 | 1.705 |
13 | 593 | 13a4620 | 1.703 |
14 | 1103 | 14a16476 | 1.714 |
15 | 1823 | 15a65606 | 1.710 |
Чи існує комп'ютерна програма, яка може обчислювати кольори?
AsciiKnots
- це комп'ютерна програма обчислення для заданої діаграми вузлів усіх забарвлених чисел шляхом обчислення нормальної форми Сміта матриці коефіцієнтів. Якщо діаграма вузлів має не надто багато перетинів, то вона також обчислюється шляхом оптимізованого методу проб і помилок пошук заданого номера забарвлення, всіх кольорів або всіх номерів забарвлення, включаючи їх забарвлення.Крім розмальовок, програма може обчислити багато більше. Його можна завантажити з
https://cariboutests.com/games/knots/AsciiKnots.tar.gz
. AsciiKnots
працює під Linux. Суворі користувачі Windows можуть безкоштовно встановити Ubuntu linux як додаток під Windows 10. Команди Linux видалити старі завантажені версії, завантажити останню версію, розпакувати її та запустити є
rm AsciiKnots.tar.gz
wget https://cariboutests.com/games/knots/AsciiKnots.tar.gz
tar xfz AsciiKnots.tar.gz
./AsciiKnots
Обмежена функція забарвлення також доступна на https://cariboutests.com/games/knots/knoteditor/ після вибору «Інструменти» > «Кольоровий вузол»
Посилання
[2] J. H. Przytycki, 3-х колірне забарвлення та інші елементарні інваріанти вузлів. Публікації Банахового центру, т. 42, "Теорія вузлів", Варшава, 1998, 275−295.
[3] Рольфсен Д., Таблиця вузлів і посилань. Додаток С у вузлах і посиланнях. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.
[4] J. C. Cha і C. Livingston, KnotInfo: Таблиця інваріантів вузлів, http://www. indiana.edu/~knotinfo
[5] «Класифікація кольорів вузлів з номером перетину до 15», https:// cariboutests.com/qi/knots/colour3-15.txt
[6] Т. Вольф, «Вузловий верстак», https://cariboutests.com/games/knots/AsciiKnots.tar.gz
Слідкуйте за оновленнями або підписуйтесь на них: