Математическое и загадочное

[Рогожников Евгений]

47 минут назад, Fireman сказал:

Написал программу для решения судоку, перебора всех вариантов решения (т.е. все вариантов выбора) и поиска самого короткого.

 

Ясно. Путь с программированием, наверно, единственный в случае, когда надо доказать невозможность решения, либо найти все возможные решения.

Иначе подобные задачи, imho совсем неинтересные.

 

48 минут назад, Fireman сказал:

Так что чем длиннее путь приходится пройти при выборе из 2х вариантов - тем сложнее судоку (но можно придумать и другие критерии).

 

Думаю,что этот критерий неверный для случая если все таки решать судоку без программирования. Минимальность пути становится ясной после полного перебора всех решений.Если же надо перебирать без помощи программы, то мне кажется, что надо делать другой перебор.

 

Лично я при переборе не всегда выбираю кейс с двумя вариантами. Хотя обычно все таки именно его. Но самый первый вариант лучше брать таким, чтобы он был "наиболее плодотворным". Строго сформулировать не готов, но идея такая- если угадывание  произойдет верно, но должно получиться открыть как можно больше всего поля. И если в итоге все же данная вилка окажется неверной, то выяснится это гораздо раньше и по итгогу все равно останется  достаточно информации, чтобы помочь при дальнейшем переборе. Если же брать только варианты из двух, то в начале решения будет много вилок. В итоге перебор будет сильно усложнен

 

[Maxim Yurchuk]

8 минут назад, Fireman сказал:

Зеленым показан последовательный ...

Да, я чет затупил. Мое решение неправильное. 

 

 

[Рогожников Евгений]

16 минут назад, Maxim Yurchuk сказал:

После этого вторая выбирает не нанятого знакомого 'C'.

 

Этого вторая фирма не сможет сделать,так как это будет ее второй ход на котором ей позволено нанимать только знакомых тех кого они уже наняли. Соответственно, они пойдут только влево или вправо.

Fireman также уже написал почему.

 

Советую все же начать решения с варианта с 3-мя гениями.

 

Ну и еще дам маленькую подсказку.Лично мне подобные подсказки часто помогают. Задача давалась школьникам на Турнире Городов в каком то далеком году.

По правилам такого турнира дается 10 задач на 5 часов. Заранее известна стоимость каждой задачи в баллах. В зачет идут 3 лучших задачи.

Иными словами, предполагается, что данная задача может быть решена ( и изложена) школьником  за довольно ограниченный по времени срок. Никакой очень сложной математики тут не нужно.

 

Хотя лично я слабо представляю, как можно успеть это сделать для случая N ( в оригинале было 11 ). Но, я не знаю решения, которое предполагали организаторы. Ориентируюсь только на свое. Возможно,есть более простое.

[Fireman]

3 минуты назад, Рогожников Евгений сказал:

думаю,что этот критерий неверный для случая если все таки решать судоку без программирования

 

ну если рассматривать именно решение, а не просто натыкал 81 цифру и опа - оказалось правильно заполненным, то всё сводится к проходу по дереву принятия решений и тут как раз возможны варианты критериев сложности

например решить судоку за 3 прохода по 2 варианта - это рассмотреть 2^3 = 8 решений, а решить судоку за 2 прохода по 3 варианты - это рассмотреть 3^2 = 9 решений

 

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

 

если предложите иной критерий - можно вместе его будет проверить

 

12 минут назад, Рогожников Евгений сказал:

Но самый первый вариант лучше брать таким, чтобы он был "наиболее плодотворным".

 

к сожалению оценить его точность вы сможете перебрав все варианты клетки :), так что если выбирать 1 из 5 на 1 клетке - это может быть очень ресурсозатратно

 

13 минут назад, Рогожников Евгений сказал:

Если же брать только варианты из двух, то в начале решения будет много вилок.

 

тут нам и требуется "идеальная удача"

 

но опять же надо оценивать сколько всего надо пройти узлов, например решая руками одну из судок мне потребовалось 8 узлов (вместо 5 идеальных), это значит, что если бы на некоторых узлах мне не везло, я бы перебрал 128 вариантов решений, отвергнув 127 из них

 

P.S.

 

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

1 угадайка  - ни одной новой найденной цифры, 2 угадайка - ни одной новой найденной цифры, 3 указайка - аналогично, 4 угадайка - полностью собранная судоку

[Fireman]

12.06.2020 в 18:16, Рогожников Евгений сказал:

1) N = 3  (легкий вариант)

 

Изменено 13 июня, 2020 пользователем Fireman

[Рогожников Евгений]

Отлично. Думаю, что тут достаточно следовать традиции древнегреческих математиков и сказать "Смотри"

[E.K.]

Всем привет,

 

> Задача давалась школьникам на Турнире Городов в каком то далеком году.

 

А почему такое радиомолчание по поводу задачки, которую типа комсомольцы должны решать за полчаса? - а? Почему не завёлся никто активный? - Про этих 11 .. боюсь, что условие задачки было поставлено не самым правильным образом. Вот, допустим, сказано было бы иначе. Например, некто с друзьями попадает в сказочный мир крафтового пива! - и там есть Самое-Особое-... ну, наверное, вы всё поняли уже.

 

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

 

Вот, хотите смеяться, но следующая задачка, которой в меня кинули, - она тоже немного ... некомфортная, мягко говоря.

 

Доска N*N, ставим N шашек на доску. Хотим сделать так, чтобы все расстояния между шашками были разными.

 

Хотите попробовать? Если честно, то я в таких задачках не очень вообще никак.. Но с удовольствием посмотрю как другие над ними плотоядничают

[Fireman]

2 часа назад, E.K. сказал:

чтобы все расстояния между шашками были разными.

имеется в виду, что N(N-1)/2 расстояний были разными?

 

а окажется, что все сводится просто к разложению Гауссовых чисел на простые множители

 

 

 

 

 

Изменено 16 июня, 2020 пользователем Fireman

[Fireman]

3 часа назад, E.K. сказал:

Доска N*N, ставим N шашек на доску. Хотим сделать так, чтобы все расстояния между шашками были разными.

 

для доски 2^N-1 x 2^N-1 решение есть  и даже для 2^N-2 x 2^N-2

Изменено 16 июня, 2020 пользователем Fireman

[Fireman]

16.06.2020 в 22:31, E.K. сказал:

Доска N*N, ставим N шашек на доску. Хотим сделать так, чтобы все расстояния между шашками были разными.

Решил посмотреть варианты, написал программу и оказалось, что для 8x8 такой расстановки шашек нет (ну или я как-то накосячил с программой)

Может стоит доказать как раз, что начиная с некоторой N такой расстановки в принципе быть не может?

 

Я свел задачу к расстановке точек на сетке (просто удобнее воспринимать)

 

Имеем следующее:

1) для N точек имеется A = N(N-1)/2 различных расстояний

2) для поля NxN точек имеется максимум B = N(N+1)/2 - 1 различных расстояний

 

этот показатель получается следующим образом: рассматриваем все возможные расстояния (я их записал в виде пары чисел - расстояния по x и по y): {1; 0}, {2; 0}, ..., {N-1; 0},  {1, 1}, {2, 1}, ..., {N-1, 1}, ..., {N-1, N-1}, расстояние {0, 0} исключается

 

3) на самом деле расстояний B будет меньше, поскольку надо исключить повторяющиеся, например: {7, 1}, {5, 5}

 

например, для поля 8x8 вместо 35 расстояний имеется только 33 расстояния, для поля 9x9 вместо 44 только 41

 

Можно предположить, что кол-во уникальных расстояний на поле NxN растёт медленнее, чем кол-во уникальных расстояний между N точек

 

Простая программка даёт вот такой результат:

 

 

при N = 17 кол-во разных расстояний на поле становится меньше, чем кол-во расстояний между 17 точками

 

Но конечно хотелось бы красивого и строгого доказательства хотя бы для N -> inf 

 

Буду думать

[Рогожников Евгений]

11 часов назад, Fireman сказал:

 

Можно предположить, что кол-во уникальных расстояний на поле NxN растёт медленнее, чем кол-во уникальных расстояний между N точек

Это не так. Как вы выше писали , количество уникальных расстояний строго равно N*(N+1)/2 - 1. Достаточно первой точкой всегда брать (0,0), а вторая точка будет пробегать все (i, j)  у которых , j<=i. Таким образом, число уникальных расстояний будет всегда ровно на N превышать число попарных расстояний А. Интуитивно, правда, ясно, что задействовать все такие расстояния не получится. Но надо думать как это доказать

[Fireman]

1 час назад, Рогожников Евгений сказал:

Это не так.

Но и это не так

 

Я же привел простой пример - есть расстояние {7,1} (7 точек вперед 1 точка вниз) и расстояние {5, 5} (5 точек вперед 5 точек вниз) - и там и там квадрат расстояния равен 50, а значит из нашего N*(N+1)/2 - 1 надо исключить 1 вариант ибо есть 2 варианта с одинаковым расстоянием.

И таким случаев с увеличением N все больше и больше и стремится (визуально) к половине всех случаев, т.е. надо рассматривать не N(N+1)/2 - 1, а ~N(N+1)/4 

 

 

Вообще мне кажется задача упирается в подсчет кол-ва способов представить натуральное число в виде сумму двух квадратов натуральных чисел, когда некоторые числа можно разложить несколькими способами

 

P.S.

 

Т.е. моя логика рассуждений - для N точек требуется N(N-1)/2 уникальных расстояний, всего на поле существует N(N+1)/2 - 1 расстояний, но некоторые расстояния совпадают.

А дальше лишь экспериментальные расчеты - что одинаковых расстояний становится все больше и больше, т.е. уникальных расстояний все меньше и меньше и в какой-то момент становится меньше, чем N(N-1)/2.

 

И вот как правильно это показать я пока думаю - в голову все формула Дирихле лезет

Изменено 18 июня, 2020 пользователем Fireman

[Рогожников Евгений]

5 часов назад, Fireman сказал:

 

Т.е. моя логика рассуждений - для N точек требуется N(N-1)/2 уникальных расстояний, всего на поле существует N(N+1)/2 - 1 расстояний, но некоторые расстояния совпадают.

А дальше лишь экспериментальные расчеты - что одинаковых расстояний становится все больше и больше, т.е. уникальных расстояний все меньше и меньше и в какой-то момент становится меньше, чем N(N-1)/2.

 

И вот как правильно это показать я пока думаю - в голову все формула Дирихле лезет

Да, это красивая идея. И хотя данная оценка явно грубая, но если нас интересует асимптотика на бесконечности, то это срабатывает. Нам нужно просто показать, что среди пар чисел (i,j), которые можно считать векторами, где i и j берутся от 0 до N, но i <=j, при больших N найдутся более N пар у которых совпадет длина векторов. Например (0,5) и (3,4); (1,7) и (5,5).

 

Доказать это можно так. Пусть m и n нечётные числа . Рассмотрим пару уравнений x+y = m; x-y=n. Она имеет одно решение в целых числах. (m+n)/2 и (m-n)/2. Но тогда x*x - y*y = m*n.

Если p и q простые числа отличные от 2, то рассмотрим число p*p*q. Это число представляется двумя способами: (p*p)*q и p*(p*q). Первый способ даст нам m=p*p и n =q.  Это даст нам решение (a,b). Второй способ даст нам m = p и n = p*q. Это нам даст решение (c,d) . При этом выполнено: a*a-b*b=c*c-d*d=p*p*q. Но тогда a*a+d*d=b*b+c*c. Значит,  вектора (a,d) и (b,c) имеют одну длину.  

 

Оценим теперь число чисел вида p*p*q в диапазоне от 0 до N*N. Каждое такое число даст нам пару векторов с одинаковой длиной. Для завершения доказательства надо показать что их будет более N. Здесь нам поможет тот факт, что число простых чисел меньших N растет как s(N)=~ N/log(N).  Рассмотрим все простые числа p и q меньшие w=N^2/3. Тогда p*p*q меньше N. Но общее число таких пар (p,q) =~ s(w)*s(w)/2. И ясно, что оно растет гораздо больше чем N.

 

 

Видно, что все эти расчеты очень грубые. Но даже они приводят к успеху для уже не очень больших N.

[Maxim Yurchuk]

45 минут назад, Рогожников Евгений сказал:

то это срабатывает

Я не уверен. Либо ошибся в расчетах ниже. 

 

Возьмем N = 100. Выберем какие-нибудь p и q < N^(2/3). Например 17 и 19. Рассмотрим n = p, n = pq.

n = 17, m = 323

Если возьмем уравнения

 x+y = m; x-y=n

И попробуем найти x,y, то получится

x =  170

y = 153 

 

Кажется, что они выходят за наше N, который равен 100. 

 

Т.е. предложенная точка лежит вне максимальной длины и не может считаться за одинаковую при доске 100х100.

[Maxim Yurchuk]

Возможно, если повторить рассуждения, но при этом взять простые p, q, r, положить 

p,q,r < N^(1/2)  

То каждая такая тройка будет давать два вектора не выходящие за поле размера N*N. 

А общее кол-во таких троек будет порядка s(N^(1/2))^3/3, что асимптотически больше N.