← Сtrl

PEHDOM · Май 31, 2019 17:19:57

py.user.next
Осталось доказать, что ряд
1/2 + 1/4 + 1/8 + … + 1/(2^n), где n->+inf
правомерен.

А почему он должен быть неправомерен. Нарисуй треугольник и подвигай по нему фишку и посмотри.

py.user.next
Можно ли складывать эти вероятности? Складывать-то можно, но говорит ли это об обходе многоугольника?

а о чем это еще может говорить? смотри 1/2**(n-1) это вероятность того что треугольник будет обойден именно на n-ном ходу. Не раньше не позже. а именно на этом конкретном ходу. Соотвевенно вероятность , например, того что фишка обойдет за 10 ходов равна вероятности того что она это сделает или на 2-м ходу или на 3-м или на 4-м …… или на 10-м . просумировав эти вероятности ты получишь вероятность того что фишка за 10 ходов обойдет треугольник..

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

py.user.next · Май 31, 2019 22:58:37

Похоже, что тут событием считается проход до какой-то вершины. Ну типа прошёл до пятой вершины в 10-угольнике - это одно событие. И вот вероятности таких событий и складываются. При сложении вероятностей событий используется правило сложения вероятностей несовместных событий P(A+B) = P(A) + P(B). Но при этом для сложения вероятностей совместных событий используется правило P(A+B) = P(A) + P(B) - P(A*B). Поэтому что-то тут не совпадает.

Что не совпадает. Например, мы имеем 1/2 + 1/4. Но если произошло событие, вероятность которого 1/4, то во время этого исхода то событие, вероятность которого равна в данном случае 1/2, тоже произошло. Значит, они совместные. И мы не можем просто взять и применить теорему о сумме несовместных событий для совместных событий.

Есть вот сумма событий (это такое определение), а есть сумма вероятностей событий (это теорема, связанная с определением). Это разные вещи. Поэтому сумма событий одна (определение одно), а теорем о сумме событий несколько (как минимум две - для совместных событий и для несовместных событий). Поэтому нельзя их смешивать и путать между собой.

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

Так что откуда там эта сумма вероятностей, из которой образуется ряд, пока неясно.

PEHDOM · Июнь 3, 2019 14:07:27

py.user.next
При сложении вероятностей событий используется правило сложения вероятностей несовместных событий P(A+B) = P(A) + P(B). Но при этом для сложения вероятностей совместных событий используется правило P(A+B) = P(A) + P(B) - P(A*B). Поэтому что-то тут не совпадает.

Еще раз повторяю, чтобы обойти весь n -угольник за k ходов нужно чтобы фишка обошла его или на первом ходу или на втором, или на третьем ….. или на k-м. Поскольку фишка движется до первого успеха то эти события несовместимы.У нас не может фишка закончить обход одновременно и на 3-й, и на 5-й ход. Следовательно для вычисления вероятности их нужно суммировать.
А P(A+B) = P(A) + P(B) - P(A*B) это вероятность не просто совместимых событий а ХОТЯБЫ ОДНОГО из двух совместимых событий.

py.user.next
У нас здесь как бы два уровня событий. Одни события происходят на элементарном уровне (один сдвиг фишки), а другие события происходят уровнем выше (один проход до вершины). И мы не можем между ними гулять, применяя одни выводы про события одного уровня к событиям другого уровня.

Нет конечно, для треугольника после первого хода все сводиться к вероятности когда два раза подряд выпадет орел поэтому там такой простой ряд. А для многоугольника там все несколько сложнее но принцип один и тот же.
Например для 4-хугольника это выглядит так:
P(1) вероятность завершить обход фигуры на этот ход.
P(2) вероятность не завершить обход фигуры на это ход но сделать это на следующий ход
(тоесть осталось обойти последнюю вершину и стоим на соседней с ней)
P(3) вероятность не завершить обход фигуры на следующий ход независимо от того куда подвинется фишка.
(или не все вершины еще обойдены, или следующим ходом независимо от выпадения монетки, фишка переместиться на уже обойденую вершину…)
Не уверен, но мне кажеться что для пятиугольника еще сложнее нужно добавлять вероятность не завершить обход фигуры на это ход но сделать это через 2 хода, для шестиугольника + еще одно условие, и так далее .. А может и нет, и этих 3-х вероятностей вполне хватит, ХЗ сейчас нет времени проверять…
Считаеться это все по формулам:
для произвольного хода k при условии что k>=4-1:

-P[k](1)=P[k-1](2)*1/2:(1-P[k-1](1)) #1/2 тут собственно шанс выпадения орла или решки
-Р[k](2)= тут пока формула не идеть... делаем по остаточному принципу 1-P[k](1)-P[k](3)
-Р[k](3)=P[k-1](3):(1-P[k-1](1))

Для квадрата АБСД, например:
ход 1: фишка двигаеться или АБ или АД .
-P1(1)=0
-P1(2)=0
-Р1(3)=1
Ход 2:фишка двигаеться по одному из возможных маршрутов:АБА, АДА, АБС, АДС.
-P2(1) = 0
-P2(2) = 1/2
-P2(3) = 1/2
ход3: АБАБ, АБАД, АБСД, АБСБ+ 4 зеркальные хода относительно диагонали АС.
Мы видим что у нас всего 8 вариантов развития событий из них только 2 приводят нас обходу всего квадрата, 2 делают возможным завершить обход на следующийх ход , и 4 делают невозможным завершить следующий ход куда бы фишка не походила. Следовательно P(1)=1\4, P(2)=1/4, P(3)=2/4.
НО это логика проврим наши формулы:
-P3(1) =Р2(2)*1/2: (1-Р2(1))= 1/2*1/2:1=1/4
-P3(2)= 1-P3(3)-P3(1)=1/4
-P3(3) = P2(3): (1-P2(1))=1/2
ход 4: АБАБА, АБАБС, АБАДС, АБАДА, АБСБА, АБСБС + 6 зеркальных ходов..
Опять же мы пока можем увидеть все варианты развития событий глазами: P(1)=1\6, P(2)=3/6, P(3)=2/6, проверяем с помощью формул:
-P4(1)=P3(2)*1/2: (1-P3(1)) =1/4*1/2: (1-1/4)=1/6
-P4(2)= 1-1/6-2/6=3/6=1/2
-Р4(3) = P3(3): (1-P3(1)) =2/6=1/3
Ход 5:
АБАБАБ, АБАБАД, АБАБСБ, АБАБСД, АБАДАД, АБАДАБ, АБСБСБ, АБСБСД, АБСБАБ, АБСБАД + 10 зеркальных.
Все еще можно увидеть что P(1)=3/10, P(2)=3/10, P(3)=4/10, формулы нам это подтвреждают:
-Р5(1)=Р4(2)*1/2: (1-Р4(1))= 3/6*1/2: (1-1/6)=3/10
-P5(2)= 3/10
-P5(3) = P4(3): (1-Р4(1))=4/10=2/5
Ход 6: тут уже многа букаф так что берем уже чистые расчеты
-Р6(1)=Р5(2)*1/2: (1-Р5(1))= 3/10*1/2: (1-3/10)=3/14
-Р6(2)= 7/14
-Р6(3) = P5(3): (1-Р5(1))= 4/14=2/7
Ход 7:ну и так далее…
-Р7(1)= Р6(2)*1/2: (1-Р6(1))- 7/14*1/2: (1-3/14)=7/22
-Р7(2) = 7/22
-Р7(3)= P6(3): (1-Р6(1))= 8/22=4/11

итоговый ряд равен 0+0+1/4+1/6+3/10+3/14+7/22+7/30+….
по идее при беконечном количестве ходов он тоже должен стрмиться к единице

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

Отредактировано PEHDOM (Июнь 3, 2019 18:15:09)

py.user.next · Июнь 4, 2019 11:22:15

Я вот думаю: что является элементарными и равновозможными событиями в этой задаче? Ведь из этого множества элементарных событий мы и должны выбрать множество благоприятных событий.

Ну например:
Если мы подбрасываем один раз шестигранный кубик, а нам нужно найти вероятность выпадения чётного числа, то мы берём все элементарные события, из них выбираем благоприятные события и потом делим благоприятные события на все события. Итого, событий возможных всего 6, так как всего шесть граней, а выпадет одна из них. Чётных чисел на кубике всего три - 2, 4, 6. Чётные числа все входят во множество всех возможных исходов. И мы просто делим 3 события на 6 событий. И получаем вероятность 3/6 или 1/2. Тут всё просто, это берётся напрямую из классического определения вероятности.

Так вот, надо как-то задачу разобрать на базовые элементы. Что занимает какую роль, шаги фишки, вершины, обход всех вершин, переход с вершины на вершину, переход в одну сторону или другую сторону. Думаю, это ключ к разгадке. Иначе так можно до бесконечности что-то вычислять и доказывать и всё будет правильно смотреться, но только не будет решением.

PEHDOM · Июнь 4, 2019 13:12:34

Эта задача по сути банальная доска Гальтона,
https://ru.wikipedia.org/wiki/%D0%94%D0%BE%D1%81%D0%BA%D0%B0_%D0%93%D0%B0%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%B0
свернутая в цилиндр(доска а не задача) и имеющая бесконечную высоту.
Изза того что она свернута в цилиндр там вероятности чуть побольше, потому что фишка может добраться до произвольной вершины большим числом способов. Но в общем принцип один и тот же.
А теперь посчитай вероятность ~~шарика во время падения~~ фишки побывать во всех столбиках(вершинах) при условии что ~~падать~~ количество ходов беконечно.

Многоуголник будет обойден тогда и только тогда когда фишка побывает в каждой вершине хотябы раз за время ~~падения~~ обхода.

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

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

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

Отредактировано PEHDOM (Июнь 4, 2019 13:34:42)

Rodegast · Июнь 4, 2019 14:54:40

Вот решение этой простенькой задачки.

 def shagomer(n):
	"""
	Возвращает среднее количество шагов за которое можно обойти n-угольник
	"""
	res = 1
	for x in range(n):
		res *= 2
	return res

С дураками и сектантами не спорю, истину не ищу.
Ели кому-то правда не нравится, то заранее извиняюсь.

py.user.next · Июнь 4, 2019 15:44:13

PEHDOM
Эта задача по сути банальная доска Гальтона,

PEHDOM
Но в общем принцип один и тот же.

Блин, в общем мы и задачу решили уже десять раз

Надо же конкретно решить, чтобы было чётко видно, где и что.

Про доску Гальтона не знал, знал только про нормальное распределение, которое доска Гальтона демонстрирует. Но нормальное распределение в этой задаче отбросил ещё в начале, так как фишка делает ходы не на любую вершину, а только последовательно и есть зависимость внутри цепочки ходов. Нормальное распределение классически демонстрируется подбрасыванием монетки. Вот в ней-то подбрасывания монетки друг с другом никак не связаны, но в итоге все выпадения орлов и решек (если их превратить в точки функции) сходятся к такому графику.

Rodegast
Вот решение этой простенькой задачки.

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

Отредактировано py.user.next (Июнь 4, 2019 15:50:35)

PEHDOM · Июнь 4, 2019 20:51:54

Rodegast
Вот решение этой простенькой задачки.

м-м-м нет, там не все так просто, для 1-угольника у тебя выходит 1 ход, хотя должно быть 0, для двухугольников у тебя 2, а должно быть 1, для теугольника 3 а по твоим расчетам 4, для квадрата у тебя 8, а долно быть 6…
полный ряд выглядит так 0, 1, 3, 6 ,10,15, 21,28,36,45,55,66,78….
задача дейсствительно простенькая, если знаешь ответ, и выглядит он так:

 def average_num_turns(n):
    """
    Возвращает среднее количество шагов за которое можно обойти n-угольник
    """
    return(sum(x for x in range(n)))

Это выясняется “методом Монте Карло”, но вот подвести под это математику пока не удалось…

py.user.next
Нужно просто что-то знать и получится короткое решение в коде.

простое решение в коде есть, см. выше.. Но вот как нему прийти с помощью математики.?

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

Отредактировано PEHDOM (Июнь 4, 2019 20:53:45)

Rodegast · Июнь 4, 2019 21:49:41

> для 1-угольника у тебя выходит 1 ход, хотя должно быть 0, для двухугольников у тебя 2

Твои рассуждения противоречат условию задачи.

> , для теугольника 3 а по твоим расчетам 4, для квадрата у тебя 8, а долно быть 6…

Вот я даже изображение многоугольника сделал. Теперь допустим что я хочу переместиться с вершины “А” на вершину “Б”, как в этом случае ты определишь среднее количество шагов?

С дураками и сектантами не спорю, истину не ищу.
Ели кому-то правда не нравится, то заранее извиняюсь.

PEHDOM · Июнь 4, 2019 22:39:27

Rodegast
Твои рассуждения противоречат условию задачи.

почему? вот условия:

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

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

Rodegast
Вот я даже изображение многоугольника сделал. Теперь допустим что я хочу переместиться с вершины “А” на вершину “Б”, как в этом случае ты определишь среднее количество шагов?

В среднем это будет 2 хода. Она туда миожет переместиться и за 1 ход, и за 3, и за 5 и за хрен знает сколько, но в среднем будет два. НО нужно ли нам это?

==============================
Помещайте код в теги:

[code python][/code]

Бериегите свое и чужое время.

Отредактировано PEHDOM (Июнь 4, 2019 22:40:42)

Python-сообщество

Уведомления

#1 Май 31, 2019 17:19:57

Легкая задача

#2 Май 31, 2019 22:58:37

Легкая задача

#3 Июнь 3, 2019 14:07:27

Легкая задача

#4 Июнь 4, 2019 11:22:15

Легкая задача

#5 Июнь 4, 2019 13:12:34

Легкая задача

#6 Июнь 4, 2019 14:54:40

Легкая задача

#7 Июнь 4, 2019 15:44:13

Легкая задача

#8 Июнь 4, 2019 20:51:54

Легкая задача

#9 Июнь 4, 2019 21:49:41

Легкая задача

#10 Июнь 4, 2019 22:39:27

Легкая задача

Board footer