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

[Valen007]

Чему равно максимальное число, равное произведению целых положительных чисел, сумма которых равна 2014?
(из олимпиад IMO)

[Незнакомка1]

Сдаёмся, ждём правильного ответа:)

[XCNY]

2014 факториал или самой сумме производных 2014.:314:

[Quanty]

3^671

[Quanty]

всё? головоломки закончились? :)

[Valen007]

3^671

Близко, но все-таки не полностью правильно.

3^671 сумма 2013 , а не 2014.

Правильный ответ
3^670*4

Доказательство будет опубликовано позже.

[Valen007]

2014 факториал или самой сумме производных 2014.:314:

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

[Valen007]

Задача 2

У игрока X долларов.
На каждом шагу игрок выигрывает доллар с вероятностью P, и проигрывает с вероятностью 1-P.
При достижении суммы в Y>X долларов игрок выигрывает.
Если игрок теряет все деньги , то он проигрывает.

Какова вероятность выигрыша, проигрыша и того, что игра никогда не остановится?

[Quanty]

Близко, но все-таки не полностью правильно.

3^671 сумма 2013 , а не 2014.



при чем тут сумма 2013? 2014 = 3*671 + 1. Произведение будет 3^671*1= 3^671.

Ну да, там с парой двоек будет оптимальнее i.e. 2014 = 3*670 + 4. Ну да рассуждения те же самые. Задача не сложная.

[Valen007]

при чем тут сумма 2013? 2014 = 3*671 + 1. Произведение будет 3^671*1= 3^671.

Ну да, там с парой двоек будет оптимальнее i.e. 2014 = 3*670 + 4. Ну да рассуждения те же самые. Задача не сложная.

по условию задачи сумма должна быть 2014, а не 2013

[Quanty]

Задача 2

У игрока X долларов.
На каждом шагу игрок выигрывает доллар с вероятностью P, и проигрывает с вероятностью 1-P.
При достижении суммы в Y>X долларов игрок выигрывает.
Если игрок теряет все деньги , то он проигрывает.

Какова вероятность выигрыша, проигрыша и того, что игра никогда не остановится?

Можно использовать условные мат ожидания, тогда все три вероятности будут удовлетворять такому рекурсивному уравнению:

P_X = P_{X+1} * P + P_{X-1} * (1-P), где P_S есть вероятность события при начальном капитале в S долларов.

Граничные условия будут разными. Например, чтобы посчитать вероятность выигрыша, надо решить это рекурсивное уравнение с граничным условием P_0 = 0, P_Y = 1.

[Quanty]

по условию задачи сумма должна быть 2014, а не 2013

опять 25….при чем тут сумма 2013?

2014 = 3*671 + 1. Произведение будет 3^671*1= 3^671. Как я сказал, я пропустил один вариант, и более оптимальное разложение есть 2014 = 3*670 + 4, нежели 2014 = 3*671 + 1.

[Valen007]

Можно использовать условные мат ожидания, тогда все три вероятности будут удовлетворять такому рекурсивному уравнению:

P_X = P_{X+1} * P + P_{X-1} * (1-P), где P_S есть вероятность события при начальном капитале в S долларов.

Граничные условия будут разными. Например, чтобы посчитать вероятность выигрыша, надо решить это рекурсивное уравнение с граничным условием P_0 = 0, P_Y = 1.

кажется, должно быть

P_X=P_{x+1}*(1-P)+P_{X-1}*P

вопрос, как это решить

[Quanty]

кажется, должно быть

P_X=P_{x+1}*(1-P)+P_{X-1}*P

вопрос, как это решить

Должно быть (согласно условию) P_X=P_{x+1}*P+P_{X-1}*(1-P). (*)

Решать рекурсивно, в зависимости от начальных и граничных условий. Например, для вероятности того, что игра не закончится P_0 = 0 и P_Y = 0, из чего нетрудно вывести, что P_X = 0 т.е. вероятность того, что игра не закончится равна нулю.

Для вычисления вероятности выигрыша начальное условие P_0 =0, граничное P_Y = 1.

Из уравнения (*) можно получить (индуктивно): P_S = ( 1 + (1-p)/p + … + ((1-p)/p)^(S-1) ) * P_1, для любого S.


В частности, для S=Y, имеем (после суммирования геометрической прогрессии)

P_Y = 1 - ((1-p)/p)^Y / ( 1 - (1-p)/p ) если P != 1/2, Y* P_1 если P= 1/2.


Теперь, используя граничное условие P_Y = 1, получаем P_1 = (1 - (1-p)/p ) / ( 1 - ((1-p)/p)^Y ), если P != 1/2, и 1/Y если P=1/2.

В итоге, P_X = (1 - (1-p)/p )^X / ( 1 - ((1-p)/p)^Y ) * P_1 если P != 1/2, и X/Y если P=1/2.

Учитывая, что вероятность бесконечной игры равна нулю, вероятность проигрыша равна (1 - вероятность выигрыша).

[Valen007]

P_x это вероятность того, что у игрока Х долларов в какой-то момент игры?

Это могло возникнуть или если у него было
1) Х+1 долларов на пред ходу и он проиграл (вероятность 1-Р)
2) Х-1 долларов на пред ходу и он выиграл (вероятность Р)

т.е. вероятность того , что у игрока стало Х долларов в какой-то момент игры

это Р_х=Р_(х-1)*Р+Р_(х+1)*(1-з) не так ли?

[Quanty]

P_x это вероятность того, что у игрока Х долларов в какой-то момент игры?

Это могло возникнуть или если у него было
1) Х+1 долларов на пред ходу и он проиграл (вероятность 1-Р)
2) Х-1 долларов на пред ходу и он выиграл (вероятность Р)

т.е. вероятность того , что у игрока стало Х долларов в какой-то момент игры

это Р_х=Р_(х-1)*Р+Р_(х+1)*(1-з) не так ли?

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

Тогда, использую условную вероятность в зависимости от исхода первого шага игры, и http://en.wikipedia.org/wiki/Law_of_total_probability получаем рекурсивное уравнение которое я написал.

[XCNY]

Как всё интерестно, а можна эток как то всё в числовых значениях ,без Х-сов У -греков и этих Р?

[Quanty]

конечно можно. Ставишь вместо X число 10, вместо Y число 20, вместо P число 1/2 :)

[Яправ]

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

Я, конечно, отвечать не буду, ато скажут что хвастаюсь...

[Quanty]

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

Я, конечно, отвечать не буду, ато скажут что хвастаюсь...

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

[Valen007]

Говоря откровенно, математическая хватка Quanty производит сильное впечатление. Ведь задачи были совсем не из легких.

[Quanty]

ага, нормальные задачи. Вторая только довольно стандартная. Один вариант её я уже видел. И вроде даже на одном из телефонных интервью решал. Только там был вариант с P=1/2, и можно было использовать свойство мартингалов, и найти надо было среднюю продолжительность игры.

[Яправ]

Говоря откровенно, математическая хватка Quanty производит сильное впечатление. Ведь задачи были совсем не из легких.

зря ты хвалишь Кванти. Задачи довольно легкие. Да и тип он неприятнейший, судя по всему, с психиатрическими отклонениями.

Математику знать это не достижение, просто, иначе нельзя:110:

[XCNY]

ага, нормальные задачи. Вторая только довольно стандартная. Один вариант её я уже видел. И вроде даже на одном из телефонных интервью решал. Только там был вариант с P=1/2, и можно было использовать свойство мартингалов, и найти надо было среднюю продолжительность игры.

И какое среднее время-продолжительности игры было с применением свойство мартингалов?

[Valen007]

зря ты хвалишь Кванти. Задачи довольно легкие. Да и тип он неприятнейший, судя по всему, с психиатрическими отклонениями.

Математику знать это не достижение, просто, иначе нельзя:110:

Первая задача была из IMO - международной математической олимпиады. Олимпиада построена так, чтобы выявить самых способных математиков до 20 лет. Так что "задачи довольно легкие" - может быть, но есть очень немногие, кто способен их решить.

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

[Quanty]

И какое среднее время-продолжительности игры было с применением свойство мартингалов?

X*(Y-X)

[Милька]

Говоря откровенно, математическая хватка Quanty производит сильное впечатление. Ведь задачи были совсем не из легких.

хех

[Quanty]

Valen007 давай следующую....впереди, пусть и не длинный, но рабочий день :)

[Valen007]

Задача из IMO.
Целые положительные числа А и В такие , что 15А+16В и 15А-16В квадраты целых положительных чисел.
Чему равно наименьшее возможное значение меньшего из двух этих квадратов?

[Яправ]

Первая задача была из IMO - международной математической олимпиады. Олимпиада построена так, чтобы выявить самых способных математиков до 20 лет. Так что "задачи довольно легкие" - может быть, но есть очень немногие, кто способен их решить.

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

не, ну если вы к модератору обратитесь, то я конечно. Модераторы у нас такие: если к ним обратился -- то хана.

теперь понятно где кванти нашел ответы.

[Quanty]

не обращайте внимания. Яправ это тролль.

[XCNY]

Задача из IMO.
Целые положительные числа А и В такие , что 15А+16В и 15А-16В квадраты целых положительных чисел.
Чему равно наименьшее возможное значение меньшего из двух этих квадратов?

:115:

[Quanty]

Задача из IMO.
Целые положительные числа А и В такие , что 15А+16В и 15А-16В квадраты целых положительных чисел.
Чему равно наименьшее возможное значение меньшего из двух этих квадратов?

Минимальное значение 9.

Полное решение A=327, B = 306, X=3, Y = 99.

Тогда 15A+16B=99^2, 15A-16B=3^2.

[Valen007]

Минимальное значение 9.

Полное решение A=327, B = 306, X=3, Y = 99.

Тогда 15A+16B=99^2, 15A-16B=3^2.

А доказательство?

[Quanty]

А доказательство?

15A+16B=Y^2,
15A-16B=X^2.

So that 30A = Y^2 + X^2, so that 3 divides X^2 + Y^2. For any integer X we have either X^2 = 0 mod 3 or X^2 = 1 mod 3, so if sum of two squares is divisible by 3 then 3 divides both X and Y.

So, the smallest value that X can take is 3. On the other hand, X = 3, Y = 99, A=327, and B=306 satisfies the above equations.

[Valen007]

15A+16B=Y^2,
15A-16B=X^2.

So that 30A = Y^2 + X^2, so that 3 divides X^2 + Y^2. For any integer X we have either X^2 = 0 mod 3 or X^2 = 1 mod 3, so if sum of two squares is divisible by 3 then 3 divides both X and Y.

So, the smallest value that X can take is 3. On the other hand, X = 3, Y = 99, A=327, and B=306 satisfies the above equations.

Seems that you solved it. Impressive!

[XCNY]

Стыдно то как, ни одну задачку не могу решить.А этоже школьнки решают и без высшей математики,правда одаренные.:239:Приедет племяш из узбекистана я ему эти задачки подкину,посмотрим ,городские первое место занимал вроде ищё в школе.А вот другие мои которые в сша,чёт чнстно говоря никак,слабенько их школьное ...:239:

[Quanty]

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


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

[Valen007]

Стыдно то как, ни одну задачку не могу решить.А этоже школьнки решают и без высшей математики,правда одаренные.:239:Приедет племяш из узбекистана я ему эти задачки подкину,посмотрим ,городские первое место занимал вроде ищё в школе.А вот другие мои которые в сша,чёт чнстно говоря никак,слабенько их школьное ...:239:

Это очень сложные задачи. Если племянник может решить какую-то из них, это , мне кажется, уже хороший результат.

[Яправ]

не обращайте внимания. Яправ это тролль.

по совместительству финалист олимпиады в США :117:

дело правда было лет 6 назад

[Quanty]

по совместительству финалист олимпиады в США :117:

дело правда было лет 6 назад

разве что паралимпиады….

[Яправ]

разве что паралимпиады….

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

[Quanty]

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

врача? LOL well, i am a doctor, but a doctor of philosophy…not a real doctor :))

[Яправ]

врача? LOL well, i am a doctor, but a doctor of philosophy…not a real doctor :))

а кто говорил что он чиропрактор? а... нукард наверное... я вас все время путаю. Оба как козлята к мужикам прикапываетесь

[XCNY]

Это очень сложные задачи. Если племянник может решить какую-то из них, это , мне кажется, уже хороший результат.

Нада будет ему закинуть из IMO ,посмотреть его подход.:115: и знания.

[Valen007]

Можно ли в таблице 11*11 расставить натуральные числа от 1 до 121 так, чтобы числа, отличающиеся друг от друга на единицу, располагались в клетках с общей стороной, а все точные квадраты попали в один столбец? (Шаповалов)

[Quanty]

ну что, репу почесал я изрядно.

Ответ будет - нет, нельзя.

Допустим есть таблица где выполняются оба условия i.e.
1) каждое число в клетке граничит с ближайшим числом и
2) есть столбец в котором только квадраты 1, 2^2, 3^2, …, 11^2.

Понятно, что столбец с квадратами не первый и не последний i.e. он разделяет таблицу на две части (иначе первое условие не выполняется).
Если это столбец номер k, то в первой части (k-1)*11 клеток, а во второй (11-k)*11 клеток i.e. кол-во клеток в каждой из частей должно делиться на 11.

Первое условие дает такую геометрическую интерпретацию: Можно провести непрерывную кривую которая последовательно проходит через все числа/клетки начиная с 1 и заканчивая 121.
Понятно также, что кривая начиная с 1 остается в одной части таблицы, затем переходит через следующий квадрат в другую часть таблицы и т.д. (e.g. начиная с 1 сначала проходит по левой части, потом проходит через 4 и оставаясь справа проходит к 9, потом оставаясь в левой части проходит к 16 и т.д.).

Разность между соседними квадратами n^2 и (n-1)^2 есть n^2 - (n-1)^2 = 2n - 1.
То есть на нашей кривой между последовательными квадратами будет 2, 4, 6, 8, 10, 12, 14, 16, 18, и 20 клеток.

Таким образом, в одной части таблицы кривая пройдет через 2 + 6 + 10 + 14 + 18 = 50 клеток, а в другой через 4 + 8 + 12 + 16 + 20 = 60 клеток. Ни то ни другое кол-во не делится на 11. Противоречие.

[XCNY]

А я ищё не закончил,чисто эмперически цыфирки раставлять по квадратикам в таблице:314:

[Valen007]

Спасибо за ответ.
Некоторое время уйдет на проверку правильности вашего решения.


ну что, репу почесал я изрядно.

Ответ будет - нет, нельзя.

Допустим есть таблица где выполняются оба условия i.e.
1) каждое число в клетке граничит с ближайшим числом и
2) есть столбец в котором только квадраты 1, 2^2, 3^2, …, 11^2.

Понятно, что столбец с квадратами не первый и не последний i.e. он разделяет таблицу на две части (иначе первое условие не выполняется).
Если это столбец номер k, то в первой части (k-1)*11 клеток, а во второй (11-k)*11 клеток i.e. кол-во клеток в каждой из частей должно делиться на 11.

Первое условие дает такую геометрическую интерпретацию: Можно провести непрерывную кривую которая последовательно проходит через все числа/клетки начиная с 1 и заканчивая 121.
Понятно также, что кривая начиная с 1 остается в одной части таблицы, затем переходит через следующий квадрат в другую часть таблицы и т.д. (e.g. начиная с 1 сначала проходит по левой части, потом проходит через 4 и оставаясь справа проходит к 9, потом оставаясь в левой части проходит к 16 и т.д.).

Разность между соседними квадратами n^2 и (n-1)^2 есть n^2 - (n-1)^2 = 2n - 1.
То есть на нашей кривой между последовательными квадратами будет 2, 4, 6, 8, 10, 12, 14, 16, 18, и 20 клеток.

Таким образом, в одной части таблицы кривая пройдет через 2 + 6 + 10 + 14 + 18 = 50 клеток, а в другой через 4 + 8 + 12 + 16 + 20 = 60 клеток. Ни то ни другое кол-во не делится на 11. Противоречие.

[XCNY]

Ответ верный.Тока доказвтельство чуток иное.Вот надыбал.

Допустим, что такая расстановка возможна. Заметим, что столбец точных квадратов не может быть ни первым, ни последним, так как у точных квадратов 20 соседних чисел, а в одном соседнем столбце можно уместить только 11 чисел. Таким образом, после удаления столбца точных квадратов, таблица распадается на две непустые части, в каждой из которых число клеток кратно 11. Группа чисел между двумя последовательными квадратами попадает в одну из этих частей, при этом числа *m2 – 1* и *m2 + 1* попадают в разные части, поэтому такие группы чисел попеременно попадают то в одну часть таблицы, то в другую. Между m2 и *(m + 1)2* имеется 2m чисел. Следовательно, в одну из частей попадет *2 + 6 + 10 + 14 + 18 = 50* чисел. Но 50 не кратно 11.

[реднек]

Шахматная доска в виде тора NxM клеток. Найти минимальное количество слонов с их позициями из которых они ходами покроют весь тор.

[Dima424]

эх... я помню 3 место на олимпиаде взял в 5м классе... аж кулькулятор подарили....

[XCNY]

эх... я помню 3 место на олимпиаде взял в 5м классе... аж кулькулятор подарили....

Хошь ищо подарю.Ток задачку реши, скок земли выкопают 2землекопа за 2часа:115:

[реднек]

ну что, репу почесал я изрядно.

Ответ будет - нет, нельзя.

Допустим есть таблица где выполняются оба условия i.e.
1) каждое число в клетке граничит с ближайшим числом и
2) есть столбец в котором только квадраты 1, 2^2, 3^2, …, 11^2.

Понятно, что столбец с квадратами не первый и не последний i.e. он разделяет таблицу на две части (иначе первое условие не выполняется).
Если это столбец номер k, то в первой части (k-1)*11 клеток, а во второй (11-k)*11 клеток i.e. кол-во клеток в каждой из частей должно делиться на 11.

Первое условие дает такую геометрическую интерпретацию: Можно провести непрерывную кривую которая последовательно проходит через все числа/клетки начиная с 1 и заканчивая 121.
Понятно также, что кривая начиная с 1 остается в одной части таблицы, затем переходит через следующий квадрат в другую часть таблицы и т.д. (e.g. начиная с 1 сначала проходит по левой части, потом проходит через 4 и оставаясь справа проходит к 9, потом оставаясь в левой части проходит к 16 и т.д.).

Разность между соседними квадратами n^2 и (n-1)^2 есть n^2 - (n-1)^2 = 2n - 1.
То есть на нашей кривой между последовательными квадратами будет 2, 4, 6, 8, 10, 12, 14, 16, 18, и 20 клеток.

Таким образом, в одной части таблицы кривая пройдет через 2 + 6 + 10 + 14 + 18 = 50 клеток, а в другой через 4 + 8 + 12 + 16 + 20 = 60 клеток. Ни то ни другое кол-во не делится на 11. Противоречие.

Ответ правильный конечно, но эта задачка слишком очевидна, я ее решил после 4 бутылок пива и 3 слайсов пицы. Вот мою решите плз.

[Quanty]

Ответ правильный конечно, но эта задачка слишком очевидна, я ее решил после 4 бутылок пива и 3 слайсов пицы. Вот мою решите плз.

всего 4-х? отлично. и какое твое решение?

[реднек]

всего 4-х? отлично. и какое твое решение?

Такое же как ни странно. Поэтому, я, собственно уверен в правильности твоего.

Вот ход мысли: 77462

Вот код для проверки:


buckets = Hash.new(0)
(2..11).each do |i|
bucket = i % 2 == 1 ? :left : :right
chain_length = i*i - (i-1)*(i-1) - 1
buckets[bucket] += chain_length
end

puts "#{buckets.inspect}"

Ключевой момент понять что непрерывные цепочки чередуются вправо и влево, далее все просто.

[Valen007]

ну что, репу почесал я изрядно.

Ответ будет - нет, нельзя.

Допустим есть таблица где выполняются оба условия i.e.
1) каждое число в клетке граничит с ближайшим числом и
2) есть столбец в котором только квадраты 1, 2^2, 3^2, …, 11^2.

Понятно, что столбец с квадратами не первый и не последний i.e. он разделяет таблицу на две части (иначе первое условие не выполняется).
Если это столбец номер k, то в первой части (k-1)*11 клеток, а во второй (11-k)*11 клеток i.e. кол-во клеток в каждой из частей должно делиться на 11.

Первое условие дает такую геометрическую интерпретацию: Можно провести непрерывную кривую которая последовательно проходит через все числа/клетки начиная с 1 и заканчивая 121.
Понятно также, что кривая начиная с 1 остается в одной части таблицы, затем переходит через следующий квадрат в другую часть таблицы и т.д. (e.g. начиная с 1 сначала проходит по левой части, потом проходит через 4 и оставаясь справа проходит к 9, потом оставаясь в левой части проходит к 16 и т.д.).

Разность между соседними квадратами n^2 и (n-1)^2 есть n^2 - (n-1)^2 = 2n - 1.
То есть на нашей кривой между последовательными квадратами будет 2, 4, 6, 8, 10, 12, 14, 16, 18, и 20 клеток.

Таким образом, в одной части таблицы кривая пройдет через 2 + 6 + 10 + 14 + 18 = 50 клеток, а в другой через 4 + 8 + 12 + 16 + 20 = 60 клеток. Ни то ни другое кол-во не делится на 11. Противоречие.

В аргументации ошибок не найдено, Решение принимается как правильное.

[azlotn01]

Перед вами математический пример:
-1-2-3-4-5-6=-7
Как видите пример не правильный, так как в нём не хватает скобок. Ваша задача расставить правильно скобки. В вашем распоряжении одна пара скобок. Запрещается добавлять и/или менять арифметические действия.

[Quanty]

Перед вами математический пример:
-1-2-3-4-5-6=-7
Как видите пример не правильный, так как в нём не хватает скобок. Ваша задача расставить правильно скобки. В вашем распоряжении одна пара скобок. Запрещается добавлять и/или менять арифметические действия.

-1-(2-3-4)-5-6=-7

[Hallucinogen]

http://img0.joyreactor.cc/pics/post/%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F-%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B3%D0%BE-%D0%B2%D0%B7%D1%80%D1%8B%D0%B2%D0%B0-%D1%88%D0%B5%D0%BB%D0%B4%D0%BE%D0%BD-%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D 0%BA%D0%B0-%D0%BF%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D 0%B0-366955.jpeg