Рогожников Евгений Опубликовано 18 июня, 2020 Share Опубликовано 18 июня, 2020 6 минут назад, Maxim Yurchuk сказал: Возможно, если повторить рассуждения, но при этом взять простые p, q, r, Согласен. Это точно срабатывает. А у меня выше была ошибка. Но хочется найти решение попроще. Я уверен, что любая расстановка N шашек просто не позволит набрать большое число уникальных путей. И там оценка будет гораздо точнее. И вообще удивлен, что дублей в уникальных длинах оказалось так много, 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
Fireman Опубликовано 18 июня, 2020 Share Опубликовано 18 июня, 2020 Вообще есть оценка для кол-ва представлений числа m в виде суммы двух квадратов: где s(m) - кол-во представлений числа в виде суммы двух квадратов Если я правильно понимаю - мы в качестве N просто подставим нашу B = N(N+1)/2 к примеру, да вообще того, что N^2 уже с понимающим коэффициентом - это на бесконечности даст нужный эффект 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
Fireman Опубликовано 19 июня, 2020 Share Опубликовано 19 июня, 2020 (изменено) 18.06.2020 в 18:26, Рогожников Евгений сказал: И хотя данная оценка явно грубая, но если нас интересует асимптотика на бесконечности, то это срабатывает. Нам нужно просто показать, что среди пар чисел (i,j), которые можно считать векторами, где i и j берутся от 0 до N, но i <=j, при больших N найдутся более N пар у которых совпадет длина векторов. Пришла в голову идея (если выше она обсуждалась - извините, пропустил) - вроде она должна сработать: Пусть у нас есть некоторая дискретная плоскость размером NxN, кол-во расстояний расчёт как O(N^2). Если мы на плоскости нарисуем окружность радиуса N, то все точки, которые лягут на эту окружность будут иметь одинаковое расстояние от центра, но при этом будут состоять из разных групп {x, y}, таким образом кол-во одинаковых расстояний будет расти как O(N). По идее этого факта в первом приближении более чем достаточно Если же более строго - тут нам на помощь придут Гауссовы числа (комплексные числа, у которых вещественная и мнимая части целые). Есть теорема Шинцеля, которая утверждает, что для любого натурального N существует окружность, которая проходит ровно через N точек решётки Z^2 (наша комплексная плоскость целых чисел). Изменено 19 июня, 2020 пользователем Fireman 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
_Иван Опубликовано 20 июня, 2020 Share Опубликовано 20 июня, 2020 (изменено) С какого-то момента решений действительно не будет --- чтобы исчерпать все большие расстояния, надо много шашек расставить в двух противоположных углах. Но тут есть отдельная интересная часть: попробовать порасставлять шашки вручную. Я сам дошёл до 5x5, и слышал, что есть решения для 6х6 и 7х7, но пока что их не раскусил. Компьютер с этим легко справится перебором, конечно. Изменено 20 июня, 2020 пользователем _Иван 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
Fireman Опубликовано 20 июня, 2020 Share Опубликовано 20 июня, 2020 1 час назад, _Иван сказал: и слышал, что есть решения для 6х6 и 7х7, но пока что их не раскусил. Ну и конечно это не единственные решения, для каждого N < 8 существует минимум 8 решений :))) 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
iv65 Опубликовано 20 июня, 2020 Share Опубликовано 20 июня, 2020 (изменено) 5 часов назад, Fireman сказал: Ну и конечно это не единственные решения, для каждого N < 8 существует минимум 8 решений :))) А причём здесь доска из 6х6? Ведь это противоречит вводной от Евгения Валентиновича: Доска N*N, ставим N шашек на доску. Хотим сделать так, чтобы все расстояния между шашками были разными. Хотите попробовать? Если честно, то я в таких задачках не очень вообще никак.. Но с удовольствием посмотрю как другие над ними плотоядничают Ведь даже в чапаевцах играют на доске 8х8. https://ru.wikipedia.org/wiki/Чапаев_(игра) И почему вы не выбрали в предложенном Вами решении доску из, например 17х17, 19х19, 23х23, либо 29х29, а также 31х31, 37х37??? Было бы гораздо красивее и полезнее в смысле математической красоты выданного Вами решения. Мы же здесь сейчас играем в шашки: ru.wikipedia.org/wiki/Шашки А не в го: https://ru.wikipedia.org/wiki/Го либо, это: https://ru.wikipedia.org/wiki/Рендзю ??? Изменено 20 июня, 2020 пользователем iv65 добавлена информация Ссылка на комментарий Поделиться на другие сайты More sharing options...
Рогожников Евгений Опубликовано 20 июня, 2020 Share Опубликовано 20 июня, 2020 45 минут назад, iv65 сказал: А причём здесь доска из 6х6? Мы уже тут доказали что для N<8 решение есть. Для N =8 решения нет. Для N больше 17 решения также нет. Судя по всему, от 9 до 16 решения также нет. Это программным перебором также несложно установить. Проблема сейчас только в том, чтобы найти более красивое решение Ссылка на комментарий Поделиться на другие сайты More sharing options...
iv65 Опубликовано 20 июня, 2020 Share Опубликовано 20 июня, 2020 1 минуту назад, Рогожников Евгений сказал: Проблема сейчас только в том, чтобы найти более красивое решение Ведь в этом всё и дело, в красоте решения математических задач собственной головой, а не простым машинным перебором. Евгений Валентинович не очень давно писал в этой ветке, что подобные решения - читерство. Ссылка на комментарий Поделиться на другие сайты More sharing options...
Fireman Опубликовано 20 июня, 2020 Share Опубликовано 20 июня, 2020 7 минут назад, iv65 сказал: а не простым машинным перебором. Евгений Валентинович не очень давно писал в этой ветке, что подобные решения - читерство. ну задача о 4 красках - решена компьютерным перебором (по другому пока не умеют) задача о хроматическом числе проверена для x=4 компьютерным перебором (по другому никак) задача о разложении числа на 3 простых множителя - решена компьютерным перебором (до 10^20, все что выше - уже строго доказывается) много задач, которые красиво нельзя (или мы пока не умеем) доказывать в полном объему 1 час назад, iv65 сказал: Доска N*N, ставим N шашек на доску. Хотим сделать так, чтобы все расстояния между шашками были разными. как мне кажется мы строго, коротко и красиво доказали, что при N стремящимся к бесконечности задача не решается доказать для 8 думаю можно строго, но красоты в таком доказательстве не будет или найти какое-то N конечное N тоже будет сложновато, хотя можно подумать, но как мне кажется чем ближе и ближе мы будем подходить к 8, тем менее красиво и более длинно будет доказательство (но это не точно :)) 1 1 Ссылка на комментарий Поделиться на другие сайты More sharing options...
Рогожников Евгений Опубликовано 20 июня, 2020 Share Опубликовано 20 июня, 2020 22 минуты назад, Fireman сказал: доказать для 8 думаю можно строго, но красоты в таком доказательстве не будет или найти какое-то N конечное N тоже будет сложновато, хотя можно подумать, но как мне кажется чем ближе и ближе мы будем подходить к 8, тем менее красиво и более длинно будет доказательство (но это не точно :)) Полностью согласен. Для 8 явно будет нудный перебор вариантов. Возможно, что то красивое может вырасти для N больших 10. Это как раз тот случай, когда компьютерный перебор имеет полное право на жизнь. На мой взгляд, fireman дал исчерпывающее решение. Ссылка на комментарий Поделиться на другие сайты More sharing options...
Vladislav Nikolaev Опубликовано 21 июня, 2020 Share Опубликовано 21 июня, 2020 07.06.2020 в 16:41, E.K. сказал: Докажите, что: 1 + 1/4 + 1/9 + … + 1/n^2 + … < 2 Вот еще так можно: Ссылка на комментарий Поделиться на другие сайты More sharing options...
Fireman Опубликовано 21 июня, 2020 Share Опубликовано 21 июня, 2020 4 часа назад, Vladislav Nikolaev сказал: Вот еще так можно: по хорошему тут надо для начала показать, что сумма меньше или равна интегралу Ссылка на комментарий Поделиться на другие сайты More sharing options...
Рогожников Евгений Опубликовано 21 июня, 2020 Share Опубликовано 21 июня, 2020 3 минуты назад, Fireman сказал: по хорошему тут надо для начала показать, что сумма меньше или равна интегралу Данное решение вообще было дано самым первым . Ссылка на комментарий Поделиться на другие сайты More sharing options...
Fireman Опубликовано 21 июня, 2020 Share Опубликовано 21 июня, 2020 43 минуты назад, Рогожников Евгений сказал: Данное решение вообще было дано самым первым . не спорю, я про конкретно тот пост, что без показа, что дискретная сумма меньше непрерывного интеграла - это неполное решение Ссылка на комментарий Поделиться на другие сайты More sharing options...
Vladislav Nikolaev Опубликовано 21 июня, 2020 Share Опубликовано 21 июня, 2020 Да, как-то не заметил, извиняюсь. Ссылка на комментарий Поделиться на другие сайты More sharing options...
Рекомендуемые сообщения
Пожалуйста, войдите, чтобы комментировать
Вы сможете оставить комментарий после входа в
Войти