На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Оставь надежду всяк сюда входящий
1) На раздел распространяются все правила форума.
2) Ответы на головоломки необходимо давать только в теге SPOILER. Сообщения в обход этого правила будут удаляться. Постоянное
нарушение данного пункта правил, повлечет за собой наказание.
3) Автор темы должен указать, известно ли ему решения задачи и сроки в которые он опубликует решение.Рекомендуется вести список отгадавших в первом сообщении.
4) При создании новой темы, в описании или в самом названии четко укажите разновидность задачи.
5) Полная версия правил раздела, находится в теме правила раздела.
Модераторы: Братец Лис
Страницы: (41) « Первая ... 37 38 [39] 40 41   ( Перейти к последнему сообщению )  
> Интересные задачки
    Цитата ya2500 @
    Так в этом и суть: ты называешь K, тебе дают K любых натуральных чисел.
    В условии этого не сказано. Более того, первое же предложение допускает толкование, что я сам выбираю числа.
    Доказательство на самом деле, чую, должно быть простое. Как в задачах о паре перчаток или о паре носков одного цвета.
    Скрытый текст
    На самом деле важны не сами значения чисел, а их остатки от деления на N. Значит числа можно заменить на эти остатки.
    Таким образом можно ограничиться числами (с повторами) из диапазона 0…N-1

    И надо доказать:
    1) что можно подобрать 2N-2 чисел из этого диапазона так, что сумма любых N из них не будет делиться на N.
    2) что добавление к любому такому набору ещё одного числа делает такой выбор возможным.

    По п. 1 можно показать, что все такие наборы содержат 0 в количестве N-1 и такого же количества ненулевого числа m (m взаимно просто с N). Такой набор позволяет получить любое ненулевое значение остатка.
    Из последнего утверждения легко вывести, что добавление ещё одного числа делает возможным получение остатка равного нулю.
    Строгое доказательство формулировать лень.

    Добавлено
    Цитата ya2500 @
    и дальше начинается алгебра ))
    С шестиугольником ты ошибся. Если посмотреть на верхний треугольник, то ясно, что длина стороны шестиугольника меньше 2. А у тебя в результате вычислений получилось почти 2.45. Правильное значение несколько меньше
    Скрытый текст
    sqrt(3) = 1.732…

    При этом левый треугольник получается прямоугольным с углами 30°, 90° и 60°. Верхний равносторонний с углами 30°, 30° и 120°. Если провести в верхнем треугольнике высоту на сторону шестиугольника, он распадётся на два треугольника подобных левому, и в два раза меньше размером.
    Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
      Цитата amk @
      С шестиугольником ты ошибся.


      Точно! Это по невнимательности:

      Скрытый текст
      Цитата ya2500 @
      12-3*x^2 = x^2
      12-2*x^2 = 0


      должно быть:

      12-3*x^2 = x^2
      12-4*x^2 = 0
      3-x^2 = 0
      x = sqrt(3)


      Добавлено
      Цитата amk @
      Строгое доказательство формулировать лень.


      блин... теперь хочу в этой жизни успеть научиться решать такие задачи)
      "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
      "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
        Цитата ya2500 @
        блин... теперь хочу в этой жизни успеть научиться решать такие задачи)
        А я её тоже ещё не решил. Там так, примерный набросок.
        Скрытый текст
        К примеру, при N = 3 не позволяют набрать сумму, кратную 3, три набора
        0 0 1 1
        0 0 2 2
        1 1 2 2
        То есть кроме описанных мною выше присутствует ещё один набор. Хотя все три набора имеют общее свойство - они содержат по 2 пары элементов.
        Думаю, аналогичный вид будут иметь наборы для больших N: два числа в количестве N-1 каждое, их разность взаимно проста N. А вот это уже можно доказать.

        Для начала возьмём набор вида 0 … 0 m … m, где m взаимно просто с N.
        Выбирая из него N чисел мы получим от 1 до N-1 чисел m, остальные нули. Остатки от деления cумм этих выборок на N принимают все значения от 1 до N-1.
        Прибавляя к этим числам любое значение мы увеличиваем суммы на число, кратное N, а значит, не меняем остатков.

        Теперь надо доказать, что любой другой набор позволяет набрать сумму кратную N.
        Случай когда m не взаимно просто с N - тривиален, в этом случае все получаемые остатки делятся на НОД(m, N), и главное, среди них присутствует 0.
        То же, когда количество чисел в наборе не N-1 и N-1. В этом случае просто выбираем N одинаковых чисел.
        Если только одно из чисел отличается (можно считать, что отличается ненулевое число), мы получаем соответствующее смещение остатков, и среди остатков появляется 0.

        А вот с наборами из совсем разных чисел надо ещё подумать.
        Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
          Про натуральные числа не понял подвоха. Достаточно взять 2 любых натуральных числа (кроме числа 2), их сумма делится на 2.

          Правка: вместо "кроме числа 2" должно было быть "делящихся или неделящихся на 2".
          Сообщение отредактировано: Mikle -
            Скрытый текст
            Цитата ya2500 @
            ты называешь K, тебе дают K любых натуральных чисел. Ты не выбираешь, какие именно числа это будут. Но тебе нужно назвать такое K, чтобы, какие числа тебе ни дали, среди них гарантированно можно было бы найти N таких, что их сумма будет кратна N.


            Цитата Mikle @
            Про натуральные числа не понял подвоха. Достаточно взять 2 любых натуральных числа (кроме числа 2), их сумма делится на 2.


            Ты называешь число 2. Тебе дают числа, допустим: 6 и 9. Их сумма не делится на 2.

            Добавлено
            И, да - при этом, N ты тоже не выбираешь. Это как "настройка задачи". То есть, могла бы быть задача, где N=2, другая задача, где N=3 и тыды. НО в нашем случае, мы имеем универсальную задачу этого типа.

            Добавлено
            Которую нужно решить для любого N.

            Добавлено
            При N=2, ответом будет 3. Каких бы три числа тебе не дали, среди них найдётся 2 таких, сумма которых будет делиться на 2.
            Сообщение отредактировано: ya2500 -
            "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
            "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
              Теперь ясно.
                Напишем строку из двух символов a и b и выделим подстроки с символа 1 до символа 2, с 2 до 4, с трех до 6, с n до 2n, пока хватит длины основной строки. Наша задача - найти такую строку, чтобы, из подстрок полученных описанным образом, никакая подстрока не входила в более длинную подстроку.

                Например, возьмём строку: 'abbbaaaaaaab'(12 символов)

                Получим такие подстроки:

                1. ab (входит в подстроку 6)
                2. bbb
                3. bbaa
                4. baaaa
                5. aaaaaa (входит в подстроку 6)
                6. aaaaaab

                Как видно, подстроки 1 и 5 не прошли проверку. Мы можем убрать последний символ, и получившаяся строка из 11 символов 'abbbaaaaaaa' проверку пройдет. Оказывается, что это и самая длинная возможная строка в алфавите из двух символов, которая удовлетворяет нашему условию.

                Максимальная длина искомой строки конечна для алфавита из любого количества букв.

                Проверьте свою интуицию, и приблизительно предположите, какой длины строку можно соорудить в алфавите из трех букв. Сто символов? Тысяча? Миллион?

                Скрытый текст
                На самом деле много больше, чем Гугол, и много больше, чем ГуголПлех.


                Гугология (это не опечатка) для программистов

                Цитата
                Было проведено соревнование по генерации больших чисел. Нет, программирование для машины Тьюринга — это все-таки слишком жестоко, поэтому использовался язык C для некоей абстрактной бесконечной машины

                Цитата
                так как BB невычислима, с этим есть технические сложности (такая функция вычислима в машинах Тьюринга с оракулами

                Сообщение отредактировано: ya2500 -
                "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                  Цитата ya2500 @
                  Проверьте свою интуицию, и приблизительно предположите, какой длины строку можно соорудить в алфавите из трех букв.

                  n в этом случае сколько брать?
                  Подпись была включена в связи с окончанием срока наказания
                    Цитата OpenGL @
                    n в этом случае сколько брать?


                    Пока хватит длины строки. То есть, если у тебя строка = 101, то будет n = 50.

                    Добавлено
                    Цитата ya2500 @
                    выделим подстроки с символа 1 до символа 2, с 2 до 4, с трех до 6, с n до 2n, пока хватит длины основной строки
                    "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                    "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                      А, ошибся, не n :) Имелось ввиду - брать подстроки так же с n до 2n, или уже с n до 3n надо?
                      Подпись была включена в связи с окончанием срока наказания
                        так же, с n до 2n
                        "Гарри Поттер и методы рационального мышления" Элиезер Юдковский
                        "Harry Potter and the Methods of Rationality" Eliezer Yudkowsky
                          Я ни разу не спец ни в теории Рамсея, ни в комбинаторике, но что-то мне подсказывает, что эта задача родственна теореме Крускала. Если это в натуре так, то рискну предположить, что ответ соразмерен чему-то вроде TREE(3)
                          Одни с годами умнеют, другие становятся старше.
                            По моим ощущениям, начиная с какого-то набора символов длина строки, которую можно подобрать, уже ничем не ограничена. После этого добавление символов к набору уже ничего не даст.
                            Или, возможно, максимальная длина представляет какую-нибудь сверх-быстро-растущую функцию наподобие (k!)!. Где k - количество символов в наборе.

                            Добавлено
                            Цитата ya2500 @
                            Оказывается, что это и самая длинная возможная строка в алфавите из двух символов, которая удовлетворяет нашему условию.
                            Последий символ этой строки не используется, поэтому его можно менять произвольно.

                            Кстати, задачу можно переформулировать.

                            Первая подстрока это строка из двух символов набора.
                            Каждая последующая получается из последней отбрасыванием первого символа и добавлением пары символов в конец, так, чтобы новая строка не содержала в себе ни одной из строк, полученных ранее.
                            При длина строки, по которой мы пробегаем получается равна удвоенной длине последней из полученной таким образом строк минус 2. Кроме того, поскольку в строках

                            Понятно, что отбрасывание символа не может привести к появлению в составе новой строки одной из уже существующих. Поэтому включение всегда захватывает один или оба последних символа более длинной строки.
                            Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                              Задача, похожая на ту, что пару страниц назад ya2500 кидал, только более сложная.
                              Прикреплённая картинка
                              Прикреплённая картинка
                              Подпись была включена в связи с окончанием срока наказания
                                Скрытый текст
                                Я на эту задачу недавно в YouTube натыкался.
                                Скрытый текст
                                Надо всего лишь построить несколько равнобедренных треугольников (проведя пару отрезков), найти среди них равносторонний, а дальше и искомый угол находится.
                                Скрытый текст
                                Искомый угол равен одному из уже обозначенных на картинке


                                А не того ли самого ролика кадр на картинке?
                                Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                                2 пользователей читают эту тему (2 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (41) « Первая ... 37 38 [39] 40 41 


                                Рейтинг@Mail.ru
                                [ Script Execution time: 0,1789 ]   [ 16 queries used ]   [ Generated: 19.04.19, 06:59 GMT ]