Пять 1000-долларовых задач Конвея

[maxal]

Руст в сообщении #919322 писал(а):

Мне кажется эта задача проще и решается от противного.
Только в условии чуть яснее станет, если писать:
каждый выпуклый регион площади 1 солержит хотя бы одну точку из М.
Иначе не будет выполнено условие - содержит ровно одну точку.

Я старался как можно ближе придерживаться к оригинальному тексту, где сказано "одну точку".
Как бы там ни было, это хороший шанс подзаработать ;)
Хотя я бы не обнадеживался раньше времени, учитывая, кто является автором задач.

[maxal]

Задача 3. The Thrackle Problem -- формулировку этой задачи я переводить не буду, так как это известная и много где описанная гипотеза.
См., например, описание в Википедии или статью Lovasz et al. On Conway's Thrackle Conjecture.

Пример трекл из Википедии:

[maxal]

Задача 2. 99-граф:
Существует ли граф на 99 вершинах, в котором каждое ребро (т.е. пара соединённых вершин) принадлежит единственному треугольнику, а каждое неребро (т.е. пара несоединённых вершин) принадлежит единственному четырехугольнику?

P.S. Доказано, что графы с указанным свойством могут существовать только на 0, 1, 3, 9, 99, 243, 6273 или 414019 вершинах, при этом для случаев 99, 6273 и 414019 вершин их существование остается под вопросом. В данной задаче предлагается ответить на этот вопрос для 99 вершин. См. также обсуждение на Mathoverflow.

[dmd]

Вариант кода для поиска числа с циклом в задаче 5

(код pari/gp)

knv()=
{
for(k=10001, 10^6,
 x= k;
 if(!isprime(x),
  print1(x,":    "); s= Set(); q= #s;
  while(!isprime(x),
   z= 0;
   alarm(20, f= factorint(x));
   g= gettime(); if(g>19000, print(); print("alarm!!!!    20 sec"); break());
   for(i=1, #f~,
    a= f[i,1]; b= f[i,2]; if(b==1, b= 0);
    da= #digits(a); db= #digits(b);
    z= z*10^(da)+a; z= z*10^(db)+b;
   );
   print1(z,"  "); x= z;
   s= setunion(s, [z]); if(q==#s, print(); print("loop!!!!    ",z); break(2), q= #s)
  );
  print(); print()
 )
)
};

[maxal]

Задача 1. Игра в чеканку
(в оригинале: "Sylver" coinage game, где Sylver - это производная от silver--серебрянный и именем Sylvester--Сильвестер, кто доказал что эта игра конечна)

В игре игроки попеременно называют положительные целые числа, которые не являются линейными комбинациями названых ранее чисел с неотрицательными целыми коэффициентами. Проигрывает тот, кто называет число 1 (и игра при этом заканчивается).
Вопрос: если первый игрок первым ходом называет число 16, и оба игрока играют оптимальным образом, то кто из них выиграет?

P.S. Чеканка здесь подразумевает монетный двор, который для каждого названного игроками числа $N$ выпускает бесконечное количество монет номинала $N$, а правила игры таким образом сводятся к называнию игроками новых номиналов монет, которые не могут быть разменены без сдачи существующими.
См. также http://en.wikipedia.org/wiki/Sylver_coinage и http://userpages.monmouth.com/~colonel/sylver/

[maxal]

А вот и видео со второй проблемной сессии, где Ковей представляет свои задачи: http://vimeo.com/109815595
Там же можно видеть других корифеев (например, Ричарда Стэнли) со своими задачами.

Первую проблемную сессию и видео пленарных докладов можно найти на сайте: http://www.math.rutgers.edu/~zeilberg/oeis50.html

[maxal]

maxal в сообщении #918975 писал(а):

Задача 5. Добраться до простого:
...
P.S. Конвей также добавил, что вполне возможно, что найдется контрпример уже в числах до миллиона -- особых численных проверок своей гипотезы он не проводил.

Не зря Конвей считал эту задачу самой простой из пяти. Не в пределах миллиона, конечно, но контрпример нашёлся:

grizzly в сообщении #1252536 писал(а):

Конвей предположил, что в конце концов всегда получится простое число. Но нет -- летом был найден контрпример.

Ссылки:
-- формулировка задачи Ковея (см. последнюю задачу в списке),
-- Первый комментарий любителя математики (не профессионала), с вопросом типа: "я нашёл, как об этом сообщить?" в каком-то популярном блоге (см. единственный комментарий внизу).
-- И уже через пару дней новость облетела весь мир.

[atlakatl]

maxal
По ссылке приведён сам контрпример:
$13532385396179 = 13\cdot53^2 \cdot3853\cdot96179 $
Первое число можно записать в виде $12\cdot10^{13}+532\cdot10^9+3853\cdot10^5+96179$
Числа не такие большие, обычной машинной арифметикой считаются. Интересно, это минимальный пример или стоит попробовать поискать? - В том числе в других системах счисления.

[maxal]

atlakatl в сообщении #1291529 писал(а):

Интересно, это минимальный пример или стоит попробовать поискать? - В том числе в других системах счисления.

Найти минимальный контрпример - серьёзная проблема, так как даже про число 20 неизвестно, является ли оно контрпримером (то есть, приведут ли итерации $f(f(\dots f(20)\dots))$ к нетривиальному циклу). Но вот найти минимальную неподвижную точку (т.е. решение $f(x)=x$), являющуюся составным числом, вполне подъемная задача.
Про другие системы счисления - примеры есть в комментариях к тому же анонсу контрпримера.

[atlakatl]

maxal
Судя по количеству и качеству контрпримеров Matt McIrvin, там поле перепахано. Но числа в других системах неожиданно маленькие.

[maxal]

atlakatl в сообщении #1291640 писал(а):

Судя по количеству и качеству контрпримеров Matt McIrvin, там поле перепахано. Но числа в других системах неожиданно маленькие.

Не знаю, насколько там перепахано, но вот этого примера в двоичной системе счисления там нет:

$$44270185196325019 = 10011|10|10100011|10111111|1101101101|10001001000100010011011_2 =$$ $$\phantom{44270185196325019} = 10011_2^{10_2}\cdot 10100011_2 \cdot 10111111_2\cdot 1101101101_2\cdot 10001001000100010011011_2.$$