Гурвич Владимир Александрович : другие произведения.

Задачки старые и новые

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:
Школа кожевенного мастерства: сумки, ремни своими руками
 Ваша оценка:
  
  Преферанс.
  
  При любой руке существуют прикуп и расклад, позволяющие взять 7 взяток при своем ходе.
  
  VG; июнь 1967; Абхазия.
  
  Подсказка: не забудьте про 78 78 78 78910
  
  ----------------------
  
  Физика.
  
  Мяч, закрученный при подаче углового, и камень (картофелина) закрученная и скользящая по асфальту отклоняются в разные стороны.
  
  VG; 1968
  
  --------------------------
  
  Шахматы. Суперпат.
  
  Существует ли шахматная позиция, в которой у Черных вообще нет ходов; в том числе и под шах? easy
  
  Может ли такая позиция возникнуть в шахматной партии? easy
  
  Каково минимальное число фигур в такой позиции? medium
  
  Какова кратчайшая партия, заканчивающаяся суперпатом? hard
  
  + Те же вопросы для взаимного суперпата: одновременно для белых и черных
  
  VG; 20 июня 2021
  
  ---
  
  Интересно, а как определяется пат в правилах шахмат.
  Если сказано, что шаха нет, но любой ход ведет под шах, - то это ошибка.
  Хотя, если уж совсем формально, - можно и так.
  Но я бы специально оговорил случай, когда вообще нет ходов.
  
  ----------------
  
   Valadimir Gurvich 19 June 2021 Игры на графах 8
  Рассматриваются ориентированные графы (орграфы). Противоположно ориентированные ребра разрешаются.
  Ядро орграфа - это множество вершин К
  а) независимое (К не содержит ребер) и
  б) поглощающее (для любой вершины v вне К найдется ребро v v', ведущее в К).
  Докажите, что:
  1. Ациклический граф имеет единственное ядро. #easy
  Теорема Бутона (1901, только для графа игры НИМ) - фон Неймана (1944) - основа теории комбинаторных игр.
  2. Четный ориентированный цикл имеет два ядра. #easy
  3. нечетный - ни одного. #easy
  4. Нечетный цикл - минимальный орграф без ядра, т.е., любой орграф без ядра содержит нечетный цикл. #medium
  Теорема Ричардсона (1953).
  Орграф без ядра называется локально минимальным, если ядро появляется при удалении любого ребра.
  5. Нечетный цикл (плюс несколько изолированных вершин) - пример такого графа. #easy
  6. Имеются и другие локально минимальные графы без ядра. #xhard
  7. Решить игру: Дан орграф без ядра. Два игрока ходят по очереди. Ход удаляет одно ребро.
  Игрок выигрывает(вариант: проигрывает) если после его хода ядро появляется.
  Не пробовал, но думаю, что #xhard
  
  Подсказка к 6:
  Ориентированный циркулянт (1,7,8)_43 не имеет ядра, но оно появляется при удалении любого ребра.
  В силу вращательной симметрии достаточно вместо 129 ребер проверить всего 3.
  Таким образом, это - локально минимальный орграф без ядра, но не минимальный.
  Он распадается на три 43-цикла
  Докажите, что (1,7,8)_к имеет ядро титтк k = 0 mod 3 или k = 0 mod 29
   Циркулянт = граф с вращательной симметрией. Группа его автоморфизмов содержит циклическую подгруппу.
  В данном примере: рассмотрите вершины правильного 43-угольника;
  проведите все стороны и все диагонали "длины" 7 и 8. Ориентируйте все ребра по часовой стрелке.
  
  
  Олег Полубасов Додуматься до такой конструкции сложновато, а уж 7 - запредел.
   
  
  Vladimir Gurvich В 1980-м Пьер Душе выдвинул гипотезу, что таких орграфов нет.
  Мол, нечетные циклы и только они - и минимальные и локально минимальные орграфы без ядра.
  [На сей раз Клод Берж к нему не присоединился. У них есть несколько совместных гипотез.
  Все подтвердились. Я подумал, что с одним Душе, без Бержа, можно и справиться.]
  Дело было в Технионе в 1995-м. Я "поставил" на циркулянты (1,7,8)_k.
  Проверил, что ядро имеется титтк k = 0 mod 3 или k = 0 mod 29. Это нетрудно.
  Студент (Апарцин) написал программу проверки. Достаточно брать k не кратное 3
  (ну и 29) и выкидывать по одному всего 3 ребра: длины 1, 7 и 8.
  Я оставил программу на ночь при ограничении k < 40. Но кто-то нажал на клавиатуру и программа слетела.
  Дело было в четверг. В субботу Технион закрыт. Я поставил на два дня для k < 45. И пример нашелся.
  
  ---
  
  VG; 25 июня 2021 Подписываюсь под гипотезой:
  Любой локально минимальный орграф без ядра имеет нечетное число ребер.
  И значит, игра на графе: "Кто создал ядро, - проиграл" - тривиальна.
  Эх, надо было вставить в статью.
  A circular graph - counterexample to the Duchet kernel conjecture;
  Discrete Mathematics 178 (1998) 229-231;
  https://www.sciencedirect.com/science/article/pii/S0012365X97818304
  
  ----------------------------------------
  
   VG; 19 June 2021 Игры на графах 8
  Дан полный граф на k > 1 вершинах , ребра которого раскрашены в n > 1 цветов (каждое одним цветом) так, что
  (*) дополнение к каждой хроматической компоненте связно (на множестве всех вершин).
  Назовём такой объект СС n-граф (СС - complementary connected).
  Например, П: k = 4, n = 2; ab, bc, cd раскрашены цветом 1, ca, ad, db цветом 2.
  Другой пример: \Delta: трехцветный треугольник.
  Докажите, что:
  (1) П и \Delta удовлетворяют (*), но
  (**) при удалении любой вершины (*) нарушается. #easy
  (2) Любой n-граф, удовлетворяющий (*) содержит П или \Delta. #medium
  (3) Только П и \Deltа удовлетворяют (*) и (**). #xhard
  (4) Решить игру: Дан СС n-граф. Два игрока ходят по очереди. Ход удаляет одну вершину.
  Игрок выигрывает (вариант: проигрывает) если после его хода (*) перестает выполняться.
  Не пробовал, но думаю, что #xhard
 Ваша оценка:
Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

Кожевенное мастерство | Сайт "Художники" | Доска об'явлений "Книги"