Перейти к содержанию

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

Участники
  • Публикаций

    47
  • Зарегистрирован

  • Посещение

Репутация

10

Информация о Рогожников Евгений

  • Статус
    Постоялец

Посетители профиля

1 120 просмотров профиля
  1. До сих пор еще не решили задачу про найм программистов. Там был решен только самый простой случай найма трех гениев. Также я не видел решения задач Сколько вариантов листа 3x3 с цифрами от 1 до 9 сгибами можно сложить в стопку клеток 1 Сколько вариантов листа 4x4 с буквами А,Б,В,Г... сгибами можно сложить в стопку в алфавитном порядке? Вами был дан только ответ без решения - 37 и 1620. Хотелось бы увидеть решение.И крайне желательно, чтобы это был не программный перебор. Для случая 3x3 это явно можно сделать. У меня для него пока получилось, что общее число способов сложить листик не более 34-х. ( пока не удалось строго доказать, что там нет дубликатов, но думаю, что нет). И тогда,так как каждый способ покрывает два варианта расстановок цифр от 1 до 9, то должно быть 68 вариантов расстановок. Над гвоздями подумаю на досуге. Времени сейчас совсем нет Прикольная задачка.
  2. Это решение приведено на странице 92. Шестиугольники в виде буквы Л, которые образуют 3-угольник. Там же и аналогичные примеры когда комнаты образуют 3-N-угольники На той же странице есть и решения в виде букв Г с завитушками. Их можно разбить на квадратики
  3. Да, вроде, с таким ограничением ничего не меняется. z^z / (z-1)^(z-1) = z * (1 + 1/(z-1))^(z-1) =~ z*e > 2*z > 1+n Тогда x^x + n*y^y <= (1+n)*(z-1)^(z-1) < z^z
  4. Полностью согласен. Для 8 явно будет нудный перебор вариантов. Возможно, что то красивое может вырасти для N больших 10. Это как раз тот случай, когда компьютерный перебор имеет полное право на жизнь. На мой взгляд, fireman дал исчерпывающее решение.
  5. Мы уже тут доказали что для N<8 решение есть. Для N =8 решения нет. Для N больше 17 решения также нет. Судя по всему, от 9 до 16 решения также нет. Это программным перебором также несложно установить. Проблема сейчас только в том, чтобы найти более красивое решение
  6. Согласен. Это точно срабатывает. А у меня выше была ошибка. Но хочется найти решение попроще. Я уверен, что любая расстановка N шашек просто не позволит набрать большое число уникальных путей. И там оценка будет гораздо точнее. И вообще удивлен, что дублей в уникальных длинах оказалось так много,
  7. Да, это красивая идея. И хотя данная оценка явно грубая, но если нас интересует асимптотика на бесконечности, то это срабатывает. Нам нужно просто показать, что среди пар чисел (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.
  8. Это не так. Как вы выше писали , количество уникальных расстояний строго равно N*(N+1)/2 - 1. Достаточно первой точкой всегда брать (0,0), а вторая точка будет пробегать все (i, j) у которых , j<=i. Таким образом, число уникальных расстояний будет всегда ровно на N превышать число попарных расстояний А. Интуитивно, правда, ясно, что задействовать все такие расстояния не получится. Но надо думать как это доказать
  9. Отлично. Думаю, что тут достаточно следовать традиции древнегреческих математиков и сказать "Смотри"
  10. Этого вторая фирма не сможет сделать,так как это будет ее второй ход на котором ей позволено нанимать только знакомых тех кого они уже наняли. Соответственно, они пойдут только влево или вправо. Fireman также уже написал почему. Советую все же начать решения с варианта с 3-мя гениями. Ну и еще дам маленькую подсказку.Лично мне подобные подсказки часто помогают. Задача давалась школьникам на Турнире Городов в каком то далеком году. По правилам такого турнира дается 10 задач на 5 часов. Заранее известна стоимость каждой задачи в баллах. В зачет идут 3 лучших задачи. Иными словами, предполагается, что данная задача может быть решена ( и изложена) школьником за довольно ограниченный по времени срок. Никакой очень сложной математики тут не нужно. Хотя лично я слабо представляю, как можно успеть это сделать для случая N ( в оригинале было 11 ). Но, я не знаю решения, которое предполагали организаторы. Ориентируюсь только на свое. Возможно,есть более простое.
  11. Ясно. Путь с программированием, наверно, единственный в случае, когда надо доказать невозможность решения, либо найти все возможные решения. Иначе подобные задачи, imho совсем неинтересные. Думаю,что этот критерий неверный для случая если все таки решать судоку без программирования. Минимальность пути становится ясной после полного перебора всех решений.Если же надо перебирать без помощи программы, то мне кажется, что надо делать другой перебор. Лично я при переборе не всегда выбираю кейс с двумя вариантами. Хотя обычно все таки именно его. Но самый первый вариант лучше брать таким, чтобы он был "наиболее плодотворным". Строго сформулировать не готов, но идея такая- если угадывание произойдет верно, но должно получиться открыть как можно больше всего поля. И если в итоге все же данная вилка окажется неверной, то выяснится это гораздо раньше и по итгогу все равно останется достаточно информации, чтобы помочь при дальнейшем переборе. Если же брать только варианты из двух, то в начале решения будет много вилок. В итоге перебор будет сильно усложнен
  12. Да, конечно,симметричное свойство. Кстати, вот решение и второго судоку. Оно у меня пошло как то легче. По той причине, что у меня получилось удачно угадать первые два раза в дереве решений. Так что ложных вилок пришлось разбирать только 4. Кстати, вопрос к Fireman. Как вам удается оценивать сложность судоку? Чуть выше вы писали, что во втором судоку придется перебирать меньше вариантов, чем в первом. Т.е получается, что у вас есть некий алгоритм, который быстро позволяет оценить такую сложность? Ну и, я думаю, будет прекрасной задачей-шуткой ( за которую в зубах бывают промежутки), если привести сложное судоку, которое не имеет решения.Т.е у которого все ветки будут приводить к тупику Таким образом, решением будет только доказательство данного факта. Я не знаю, как решают судоку метры, но если решать так как я - путем "блуждающего" перебора, то я бы и за неделю не решил.
  13. Попытка номер 2. На этот раз, вроде, ничего не напутал
×
×
  • Создать...