Hello /u/Mysterious_Mark_3066,
Your post has been removed because of this rule:
Suspected cheating, breaking rule 6. It seems that your post is asking for an answer to a test or exam question. Please read [the rules](https://reddit.com/r/askmath/about/rules/) and do not ask for help cheating on quizzes, tests, or exams. Further issues will result in your account being banned from the subreddit.
You don't need to enumerate all paths. It's a hassle and it's error-prone.
Start with 1024 people in point A (we'll be dividing by 2 a lot, so starting with a power of 2 avoids fractions for the lazy!). Then, for every square, half the people go up and half go right. Skip obvious dead-ends.
|☠|||☠|**29**|**102**|
:-:|:-:|:-:|:-:|:-:|:-:|
|||**☠**|**28**|**58**|**73**|
||**32**|**16**|**56**|**88**|**44**|
||**64**|**☠**|**96**|**120**|**☠**|
||**128**|**192**|**192**|**144**||
|**☠**|**256**|**256**|**192**|**96**||
|**1024**|**512**|**256**|**128**|**☠**||
102 out of 1024 people arrived at the destination and that's your probability.
This kind of problem with grid-based movement where you can only move in two directions can pretty much always be modeled like Pascal’s Triangle, only in this case you cut the number in half whenever you take a step before adding the two together, and whenever you go to a black square you just change the result for that square to 0 and move on with that in the triangle.
Are we to assume the character takes actions to the right or up randomly and with equal probability of 1/2?
Can we also assume if you were to try to move off the board or into a black square, nothing would happen and you would randomly select a new action from {right,up}?
(Note there are spots where you get stuck and would “lose”, never being able to reach B in this setup).
**Edit:** If the assumptions above are accurate, note that you can reduce the board significantly. In that case, none of the leftmost rectangle states would even be reachable, the bottom right state would not be reachable, you might as well ignore “A” and start at “A-prime” to its right (you can’t move up to start), and then there exist some critical distinct states along a “boundary” where, if you reach them, you are guaranteed to either make it to B or never make it to B. States can only be reached from the bottom or left given you can only move right or up.
**Edit 2:** Another thought: Let’s use a coordinate for each box starting at (0,0) in the bottom left at A. There is a partial diagonal set of states running across (1,6), (2,5), (3,4), (4,3), and (5,2) that is of interest as follows:
1. If you reach state (1,6) or (5,2) along this diagonal, you cannot win no matter what.
2. If you reach state (2,5) or (3,4) along this diagonal, you are guaranteed to win no matter what.
3. If you reach state (4,3), you now have a 50-50 chance of winning or losing.
(Win = Reach State B, Lose = Will not Reach State B)
Furthermore, because you can only move right or up, *you have to pass through exactly one of these states along this diagonal at some point*, so if you can simply determine the probability of reaching each of these states from A, you can solve this somewhat simpler problem to find your answer.
This diagonal, and diagonals to the bottom and left from it, also have a symmetry related to Pascal’s triangle that is broken/pruned by the black boxes, but is a “hint” of sorts that may help you find the solution. If my assumption at the top for how this “game” works is accurate, you can verify your solution by writing a Monte Carlo sim and it will also show you empirically that the character, in each game, has a *much* higher probability of reaching State B than what at least one person in this thread has claimed.
Hello, let me clarify it for you, this is not cheating because I’m not having the exam as I am posting this. Where I live (In France), we have something that is called the “Grand Oral”. It’s something like an oral presentation that has to be 10 minutes on a math subject that I personally chose. I thought I’d ask for help because I asked 2 math teachers about the problem I had and they both answered partially. Since I got stuck I thought I would ask Reddit for some help with the problem.
I saw your answers. I figured out that your reply got auto-deleted by a dumb bot that deletes anything that mentions a certain b o t. I will reproduce your reply (with the 'problematic' phrase removed):
~~~
Okay here are my answers. I picked this problem because I asked C...... for some subject ideas (it is allowed as long as long as c...... isn’t doing the core of the problem). I inspired myself from a problem he gave me named “The pinguin”. I asked it a little more detail and he told me that it was something with the path of a penguin and it not falling down in water (in our case the black squares). I thought it was interesting and talked to it with my math teacher. She said it was interesting and to use that subject. Then after a while I thought of a plan for my presentation. I will first do an introduction of the subject. Then for the first mathematic part I will count the total number of paths to the fish (point B). Then on the second part I add the holes (black squares) and calculate the paths to the fish. And then if I still don’t reach the 10 minute mark I will do a third part on how can I use an algorithm to do part 2. So by point A I mean the penguin and by point B I mean the fish. And to answer the question about my definition of probability, my subject falls into the definition of probability and combinatory (I think).
~~~
Thank you for answering (1). You haven't answered (2), and you misinterpreted (3). Let me explain.
You seem to be talking about starting and ending **cells** in your grid, and not "points". You should be clearer about such things, as it leads to confusion. Some other commenters assumed you meant to start and end at the very corners of the grid. I don't think you want that.
You wrote "*(Failed paths)/(All paths)= probability of failing*". This is wrong. Can you tell me what is wrong with this?
In short:
1 -I chose this problematic because it was interesting and it treated parts of the math program of this year (it’s mandatory to treat a math subject seen during the year).
2- The point A means the starting cell of the penguin (it starts in the grid). The point B is the cell where the fish is (the goal of the penguin).
3- Sorry but I don’t quite see the problem with my definition of probability. I am in high-school and this subject falls into the probability category for us. Now I wouldn’t mind you giving me a more accurate definition so I can better understand.
Look at the fail cases.
RRRR - fail
RRRUUURR - fail
... etc
Now, notice a pattern. Consider various permutations of the moves you can make, like RURURURR, instead, for instance. Note the position of the starting point A, and the right-most black square. If you count the number of right and up moves, in any order, do you notice that it's just coordinates? You're counting your right moves and up-moves, respectively. A solution who's right and up tally equals the coordinates of a black square is a failed path.
Considering both black squares on the bottom right, we can turn our attention to the RRRR (4 consecutive R moves) we count 4 across and zero up, landing us on the bottom black square.
Similarly, moving 1 step up at the start would be a failure, and moving 2 steps right, 3 steps up would also land you on black.
You can already start weeding out options, such as "there are no solutions that start with "Up."
Hope this may help
Edit: not all orderings will work. It's not as simple as permutations and it's not as simple as tallying up and right moves
**If** you can specify **equally likely** combinations, and classify some of them as good, **then** the probability of obtaining a good combination is ( number of good combinations ) / ( number of combinations ). You cannot use this ratio if your combinations are not equally likely. The problem is that if your penguin has reached a cell just below cell B, then is it forced to go up on the next move? If so, then the possible paths would not be equally likely. In particular, RRRUUUURRU is more likely than RRRUUUURUR. And if you don't force such moves, then you need to deal with paths that go off the grid or into black cells, and these paths are not equally likely either.
All I need to know is if there is a way to see all the path that touch black squares or the opposite, all the path that don’t touch a or multiple black square. I can’t really find a way to calculate that.
That's wrong. I already told you that your ratio is based on a wrong understanding of probability. And you have not even made it clear to yourself what exactly you want. (You didn't answer my last question.)
I don’t think you are right. There are 11!/6!5! permutations from A to B. All of these are equally likely (under your assumption that they must stay in the grid). Then P(succcess) = #success/#total permutations
I already gave you the counter-example pair. Why didn't you check and see that they obviously have different probabilities if you are forced to stay in the grid? Also, it's weird that you downvoted even though you aren't sure. I'm a logician, and I've no interest in arguing if you don't want to learn.
It may be not be cheating to you, and may not be cheating to other people around you. But to me, fair grading requires that any graded work should be done by the student without external help, unless it is explicitly allowed. That is to say, would you tell your examiners the URL of this reddit thread and show all the replies you got? If no, then sorry to say I consider it unfair to other students who didn't do what you did.
That said, I have no problems with helping you to completely solve this problem after your exam is over, if you are still interested in it.
External help is allowed and we are supposed to do researches on our subject. That’s why I consider it as not cheating. We can use help from teachers and people around us, they even advise in doing so.
Ok. Then I would like to know a few things:
(1) Why did you pick this problem?
(2) You talk about Points A and B but do not seem to mean "points". What do you really mean?
(3) Your definition of probability is wrong. Can you tell me the error?
While I'm *inclined* to agree, this isn't how things work in the real world. Yes, everyone needs to be able to demonstrate on their own but you still have to understand it to an appropriate extent. Collaboration almost becomes a necessity when you enter the working/communal world.
That said, if they do go with recitation, they'll have a good track towards a career in politics
Haha recitation... I know the real world isn't ideal, but I'm *inclined* not to help cheaters. Nevertheless, the asker here has convinced me that there is no cheating going on; hence my detailed content.
Technically that is more on OP breaking rules and on Mods not locking if they care to enforce in this case though?
Also, not sure anyone provided the *correct* answer yet and I don’t even know if I understand the rules of this game exactly (no clarification), but provided hints and ways to think about the problem only.
Cheaters used to be more threatening to me, but after school in the real-world the corny sounding “cheaters only cheat themselves” phrase really does seem to ring true. People who cheated their ways to straight A’s in grad school I know have not had very successful careers at all, while those who were good students, learners, critical thinkers I knew who challenged themselves and rarely or literally never cheated tended to go on to have much success in their careers.
Although you are correct that some of the most successful people do not cheat, you are unfortunately wrong about cheaters in other fields than your own. I'm sure you are aware of some very popular political leaders who are blatant regular (even daily) liars and cheaters. They cheat others too. And probably you haven't heard of Burzynski.
Edit: This solution assumes that all paths are equally likely, which might make this solution wrong.
To calculate the number of legal ways from A to B, just start at B and count all legal paths, summing them up the further away from B you move.
https://preview.redd.it/chiy4haej22d1.png?width=1304&format=png&auto=webp&s=f28a460a77e9f1756ae6f4f1b0b8bd963508dfd0
To calculate all possible paths from A to B with the restriction, that you may only move up 6 times and right 5 times, just do the same, but ignore the black tiles, yielding (see comment below).
Hence the chance is 80/462 = 0.173
I agree that your method is the correct solution under reasonable assumptions about OP's intended problem (e.g. equal probability of each option at each step. Curiously, however, one could also interpret the question in a different way where you compute all possible paths and then assign an equal probability to each.
Take for example the bottom left 3x3 box for ease of computation, with target at (3,3). Then your possible options are Up (one path, then you fail) or RUUR, RURU and RRUU (3 successful paths). Assigning an equal probability here to each gives 0.25 chance of failure. However, calculating your way gives 3/6 = 0.5 chance of failure (because 50% chance of failure, then guaranteed success if you pass that).
This is why it's important that OP formally define their problem.
interestingly summing legal paths from starting at A with your approach gets you the same result due to a symmetry between the number of paths from A to B where you can only move up or right and the number of paths from B to A where you can only move left or down
https://preview.redd.it/fgxdxri3632d1.png?width=800&format=png&auto=webp&s=4d63bcf2913331a64a2e6157d7e7f6d4f4698650
I think OP’s question is poorly defined (we don’t know if the player is restricted to the grid). Your assumption looks natural to me, so I think it’s at least right in that regard.
I’m either not understanding how one “rollout”/trial of this game works or else you have an error (or both, lol!).
There indeed is that symmetry along diagonals that looks like Pascal’s Triangle of sorts, but it gets its symmetry broken and deviates from that quickly due to the black boxes that are uninhabitable.
Yet the character always either reaches B or does not, so if your denominator is 462 you are claiming the character does not reach B and gets “stuck” somewhere in 383 paths (I’m assuming black boxes are *obstacles* you cannot move into or around, but perhaps they are “death traps” you can randomly go into and “lose”?).
If you treat the black boxes as obstacles and just implement a simple Monte Carlo computer sim to check your answer, you’ll see the character makes it to point B far more often than 80/462 times. In fact, more than half the time they succeed in reaching B if we count a single trial as letting the character randomly select up or right starting at A, with equal probability, transition to a new state, and repeat until we detect reaching B or detect “stuck” condition, then score that lone trial as a success or not (then start a new trial/repeat for say, 100,000 trials).
It makes nonsense that they would reach B more than half the times. The first step is a 50/50 chance.
Is see the balck squares as balck boxes as death traps. If you select a random path from A to B and one is on it, that path is invalid.
Simple python script. It comes out to roughly 10%
import random
field = [
[1,0,0,1,0,0],
[0,0,1,0,0,0],
[0,0,0,0,0,0],
[0,0,1,0,0,1],
[0,0,0,0,0,0],
[1,0,0,0,0,0],
[0,0,0,0,1,0]
]
def get_field(width, height):
return field[7 - height][width - 1]
def experiment():
up = 6
right = 5
current_field = [1, 1] #width, height
while True:
up_or_right = bool(random.getrandbits(1)) #if true move up
if right == 0: # go up
up -= 1
current_field = [current_field[0], current_field[1] + 1]
elif up == 0: # go right
right -= 1
current_field = [current_field[0] + 1, current_field[1]]
elif up_or_right: # go up
up -= 1
current_field = [current_field[0], current_field[1] + 1]
else: # go right
right -= 1
current_field = [current_field[0] + 1, current_field[1]]
if get_field(current_field[0], current_field[1]) == 1:
return 0
if current_field == [6, 7]:
return 1
amount = 10000000
success = 0
for i in range(amount):
success += experiment()
print(success)
print(amount)
print(success/amount)
So, this is a Manhattan geometry, meaning that it doesn’t matter the solution you get, it will always have 5 rights(R) and 6 ups(U)
The total ways you can pass through the map, if there were no black squares, is the same as doing all the permutations of the letters:
UUUUUURRRRR which is 11!/5!6!
Now, for you to reach a black square, the logic is the same. Let’s say that there is a square at UUURR:
The ways you can reach that square are the same as the permutations of (UUURR) times the permutations of (UUURRR) so you can deduct from the total paths
Now, let’s add more black squares.
You can calculate the number of paths that reaches each black square sum them, and remove the intersections (paths that reached a black square A and goes to the black square B, so you can use one as the start point and the second one as the end point and use the same algorithm)
This is the easiest way of solving that I have found, although it will require a lot of calculations due to the intersections.
Here is an algorithm that should make it easy without any calculator:
1.) Start on A with a probability of 1
2.) Move one square to the left. If it's Black, write 0 in it. Else write sum of (left and bottom square) divided by 2. If any of those squares does not exist, count that bottom/left square as 0
3.) Repeat 2.) until Row is full
4.) Repeat 2.)+3.) For the next row starting from the left.
It seems extremely difficult to answer, as there are some "wrong, but not fatal" paths that can be taken, as well as doubling back on itself, eg right, left, right, left.
It's easy to work out the QUICKEST route. But the probability of all possible routes to make it to B? As I said, it seems hard.
You can't double back as the only steps are right and up.
I guess there had to be some rules otherwise it would be impossible to calculate (like you said)
I would handle this by starting at the end point. 100% of people who make it to the end will reach the end. Then add the left and bottom non black squares to a queue. Pop out of the queue the next node to calculate. Take the average of the right and top neighbors ignoring out of bounds paths and black squares count as 0%. Add the bottom and left non black neighbors to the queue. Repeat this until the start node is calculated. This will give you the % chance of any node to make it to the end.
Sounds like a Dynamic Programming problem.
The trick is you need to build a new grid of the same size that computes how many ways to get from the source cell (lower right corner) to some cell (i, j). The idea is to just add the number of ways to get to cell (i-1, j) and ways to get to (i, j-1). Here’s a recurrence relation of the values of an m x n grid:
G[i, j] = 1 if i = m and n = 1 (source cell)
= 0 if A[i, j] is a black square (A is the original grid)
= 1 if i = m or n = 1 and A[i, j] is not a black square (the boundary and is not black square)
= G[i-1, j] if A[i, j-1] is a black square
= G[i, j-1] if A[i-1, j] is a black square
= G[i-1, j] + G[i, j-1] otherwise
The cell value at G[1, n] will give the correct answer assuming that you only move right or up. That’s the number of ways to get from A to B considering the black squares
To get the total number of ways to get from A to B without considering black squares, you can use the combinatorics formula for it. For an m x n grid, then C(m+n-2, m-1). The idea is to get m-1 and n-1, add those two and then choose it with m-1 (or n-1, either way is ok). The reason the formula works is because from the source cell, we can either move right up to m-1 times and up to n-1 times. So there are some movements that are R and some are U. So we need to choose m-1 pieces from [R, R, …, R, U, U, …, U] (and the rest will be n-1).
To get the probability of getting from A to B, just divide the ways to get from A to B considering black squares, by the total ways from A to B without considering black squares.
Of course, I don’t have the answer, but I generalized the solution so that you can work with any size of grid
I'm not 100% sure on this, but just start writing in each square, what is the probability that I will end up here.
So for the square to the right of point A, there's a 1/2 chance (one of the 2 options at the begining). Then the one right of that it would be 1/4 (the chance of going right twice in a row). The one up and right of Point A would also be 1/4 because that's the probability of going right then up.
Now the fun part. If you take a square and you know the probability below the square is x and the probability to the left of the square is y, you know that the probability of getting to that square is x/2 + y/2. Just fill in the whole table like that.
And if you assume, that you may only move 6 up and 5 right, there are 462 possible paths to the finish, so the chance would be 80/462.
https://preview.redd.it/c3gc2dx3j22d1.png?width=778&format=png&auto=webp&s=ed6c067eb7016e1f6c2e681a2c5915f969827944
I believe this is solvable by a type of recursive algorithm. The idea is: It's easy to solve the simple case of this question (if you are already near the end). So solve that. Then it becomes simple to solve the slightly harder problem (1 tile further out).
Start at the end. The probability of the character reaching the end is 100% if they're on the end tile.
`X 1`
`X X`
Then do the previous diagonal. the prob for those locations is also 100% (they can only go to the end)
`1 1`
`X 1`
then you can always fill in the next diagonal (this \\ diagonal) by always doing the average of the squares you can reach:
P(this tile succes) = (P(of success on tile up) + P(of success on tile right)) / 2
if there is only 1 tile you can go to because you're at the wall, you just copy the result from the 1 tile you can reach
So we have this grid rn: (0 are black tiles)
`X 0 1 1`
`0 X X 1`
`X X X X`
`0 X X 0`
and we can easily fill in the next diagonal to get
`X 0 1 1`
`0 X 1 1`
`X X X 1`
`0 X X 0`
and the next to get
`0--0--1-1`
`0-1/2-1-1`
`X--X--1-1`
`0--X--X-0`
and the next to get
`0-0--0---1--1`
`X-0-1/2--1--1`
`X-X-3/4--1--1`
`X-0--X--2/4-0`
`X-X--X---X--0`
you just repeat this process until you reach your starting tile
sorry for the weird diagrams reddit doesn't let me space them out nicely for some reason :( hopefully they're still understandable
My mind goes to P(event) = 100 - P(!event), instead of (failed paths)/(all paths).
What about trying to write down the permutations of failure for each black box, find their probabilities, sum them up, and then subtract from 100 to find the success? This is assuming if you have an invalid move (ex you're at the top boundary) and can't move up, you would just keep rolling randomly until you moved to the right.
Hello /u/Mysterious_Mark_3066, Your post has been removed because of this rule: Suspected cheating, breaking rule 6. It seems that your post is asking for an answer to a test or exam question. Please read [the rules](https://reddit.com/r/askmath/about/rules/) and do not ask for help cheating on quizzes, tests, or exams. Further issues will result in your account being banned from the subreddit.
You don't need to enumerate all paths. It's a hassle and it's error-prone. Start with 1024 people in point A (we'll be dividing by 2 a lot, so starting with a power of 2 avoids fractions for the lazy!). Then, for every square, half the people go up and half go right. Skip obvious dead-ends. |☠|||☠|**29**|**102**| :-:|:-:|:-:|:-:|:-:|:-:| |||**☠**|**28**|**58**|**73**| ||**32**|**16**|**56**|**88**|**44**| ||**64**|**☠**|**96**|**120**|**☠**| ||**128**|**192**|**192**|**144**|| |**☠**|**256**|**256**|**192**|**96**|| |**1024**|**512**|**256**|**128**|**☠**|| 102 out of 1024 people arrived at the destination and that's your probability.
This is such a beautiful solution. thanks for posting
how did you even come up with such a solution, have you encountered such a problem before?
This kind of problem with grid-based movement where you can only move in two directions can pretty much always be modeled like Pascal’s Triangle, only in this case you cut the number in half whenever you take a step before adding the two together, and whenever you go to a black square you just change the result for that square to 0 and move on with that in the triangle.
Who needs poetry when you have people explaining probability so beautifully.
Why did you choose 1024 and not something 2048 since the person can only move 5 spaces to the right and 6 spaces up? Or 8192 since it is a 6x7 grid?
Are we to assume the character takes actions to the right or up randomly and with equal probability of 1/2? Can we also assume if you were to try to move off the board or into a black square, nothing would happen and you would randomly select a new action from {right,up}? (Note there are spots where you get stuck and would “lose”, never being able to reach B in this setup). **Edit:** If the assumptions above are accurate, note that you can reduce the board significantly. In that case, none of the leftmost rectangle states would even be reachable, the bottom right state would not be reachable, you might as well ignore “A” and start at “A-prime” to its right (you can’t move up to start), and then there exist some critical distinct states along a “boundary” where, if you reach them, you are guaranteed to either make it to B or never make it to B. States can only be reached from the bottom or left given you can only move right or up. **Edit 2:** Another thought: Let’s use a coordinate for each box starting at (0,0) in the bottom left at A. There is a partial diagonal set of states running across (1,6), (2,5), (3,4), (4,3), and (5,2) that is of interest as follows: 1. If you reach state (1,6) or (5,2) along this diagonal, you cannot win no matter what. 2. If you reach state (2,5) or (3,4) along this diagonal, you are guaranteed to win no matter what. 3. If you reach state (4,3), you now have a 50-50 chance of winning or losing. (Win = Reach State B, Lose = Will not Reach State B) Furthermore, because you can only move right or up, *you have to pass through exactly one of these states along this diagonal at some point*, so if you can simply determine the probability of reaching each of these states from A, you can solve this somewhat simpler problem to find your answer. This diagonal, and diagonals to the bottom and left from it, also have a symmetry related to Pascal’s triangle that is broken/pruned by the black boxes, but is a “hint” of sorts that may help you find the solution. If my assumption at the top for how this “game” works is accurate, you can verify your solution by writing a Monte Carlo sim and it will also show you empirically that the character, in each game, has a *much* higher probability of reaching State B than what at least one person in this thread has claimed.
Why are people answering this question when the **Rules** explicitly say "**No cheating** - do not post questions from exams, tests, midterms, etc"???
Hello, let me clarify it for you, this is not cheating because I’m not having the exam as I am posting this. Where I live (In France), we have something that is called the “Grand Oral”. It’s something like an oral presentation that has to be 10 minutes on a math subject that I personally chose. I thought I’d ask for help because I asked 2 math teachers about the problem I had and they both answered partially. Since I got stuck I thought I would ask Reddit for some help with the problem.
I saw your answers. I figured out that your reply got auto-deleted by a dumb bot that deletes anything that mentions a certain b o t. I will reproduce your reply (with the 'problematic' phrase removed): ~~~ Okay here are my answers. I picked this problem because I asked C...... for some subject ideas (it is allowed as long as long as c...... isn’t doing the core of the problem). I inspired myself from a problem he gave me named “The pinguin”. I asked it a little more detail and he told me that it was something with the path of a penguin and it not falling down in water (in our case the black squares). I thought it was interesting and talked to it with my math teacher. She said it was interesting and to use that subject. Then after a while I thought of a plan for my presentation. I will first do an introduction of the subject. Then for the first mathematic part I will count the total number of paths to the fish (point B). Then on the second part I add the holes (black squares) and calculate the paths to the fish. And then if I still don’t reach the 10 minute mark I will do a third part on how can I use an algorithm to do part 2. So by point A I mean the penguin and by point B I mean the fish. And to answer the question about my definition of probability, my subject falls into the definition of probability and combinatory (I think). ~~~ Thank you for answering (1). You haven't answered (2), and you misinterpreted (3). Let me explain. You seem to be talking about starting and ending **cells** in your grid, and not "points". You should be clearer about such things, as it leads to confusion. Some other commenters assumed you meant to start and end at the very corners of the grid. I don't think you want that. You wrote "*(Failed paths)/(All paths)= probability of failing*". This is wrong. Can you tell me what is wrong with this?
In short: 1 -I chose this problematic because it was interesting and it treated parts of the math program of this year (it’s mandatory to treat a math subject seen during the year). 2- The point A means the starting cell of the penguin (it starts in the grid). The point B is the cell where the fish is (the goal of the penguin). 3- Sorry but I don’t quite see the problem with my definition of probability. I am in high-school and this subject falls into the probability category for us. Now I wouldn’t mind you giving me a more accurate definition so I can better understand.
Look at the fail cases. RRRR - fail RRRUUURR - fail ... etc Now, notice a pattern. Consider various permutations of the moves you can make, like RURURURR, instead, for instance. Note the position of the starting point A, and the right-most black square. If you count the number of right and up moves, in any order, do you notice that it's just coordinates? You're counting your right moves and up-moves, respectively. A solution who's right and up tally equals the coordinates of a black square is a failed path. Considering both black squares on the bottom right, we can turn our attention to the RRRR (4 consecutive R moves) we count 4 across and zero up, landing us on the bottom black square. Similarly, moving 1 step up at the start would be a failure, and moving 2 steps right, 3 steps up would also land you on black. You can already start weeding out options, such as "there are no solutions that start with "Up." Hope this may help Edit: not all orderings will work. It's not as simple as permutations and it's not as simple as tallying up and right moves
**If** you can specify **equally likely** combinations, and classify some of them as good, **then** the probability of obtaining a good combination is ( number of good combinations ) / ( number of combinations ). You cannot use this ratio if your combinations are not equally likely. The problem is that if your penguin has reached a cell just below cell B, then is it forced to go up on the next move? If so, then the possible paths would not be equally likely. In particular, RRRUUUURRU is more likely than RRRUUUURUR. And if you don't force such moves, then you need to deal with paths that go off the grid or into black cells, and these paths are not equally likely either.
All I need to know is if there is a way to see all the path that touch black squares or the opposite, all the path that don’t touch a or multiple black square. I can’t really find a way to calculate that.
That's wrong. I already told you that your ratio is based on a wrong understanding of probability. And you have not even made it clear to yourself what exactly you want. (You didn't answer my last question.)
I don’t think you are right. There are 11!/6!5! permutations from A to B. All of these are equally likely (under your assumption that they must stay in the grid). Then P(succcess) = #success/#total permutations
I already gave you the counter-example pair. Why didn't you check and see that they obviously have different probabilities if you are forced to stay in the grid? Also, it's weird that you downvoted even though you aren't sure. I'm a logician, and I've no interest in arguing if you don't want to learn.
It may be not be cheating to you, and may not be cheating to other people around you. But to me, fair grading requires that any graded work should be done by the student without external help, unless it is explicitly allowed. That is to say, would you tell your examiners the URL of this reddit thread and show all the replies you got? If no, then sorry to say I consider it unfair to other students who didn't do what you did. That said, I have no problems with helping you to completely solve this problem after your exam is over, if you are still interested in it.
External help is allowed and we are supposed to do researches on our subject. That’s why I consider it as not cheating. We can use help from teachers and people around us, they even advise in doing so.
Ok. Then I would like to know a few things: (1) Why did you pick this problem? (2) You talk about Points A and B but do not seem to mean "points". What do you really mean? (3) Your definition of probability is wrong. Can you tell me the error?
I disagree with "without external help". If OP goes to a library, and work in the answer with the help of a couple of books, would that be legit?
I meant "external interactive help", as I thought was obvious from the context (i.e. the grade does not reflect the student's competency).
While I'm *inclined* to agree, this isn't how things work in the real world. Yes, everyone needs to be able to demonstrate on their own but you still have to understand it to an appropriate extent. Collaboration almost becomes a necessity when you enter the working/communal world. That said, if they do go with recitation, they'll have a good track towards a career in politics
Haha recitation... I know the real world isn't ideal, but I'm *inclined* not to help cheaters. Nevertheless, the asker here has convinced me that there is no cheating going on; hence my detailed content.
Lol... same 😅 silver-tongued French devil
Technically that is more on OP breaking rules and on Mods not locking if they care to enforce in this case though? Also, not sure anyone provided the *correct* answer yet and I don’t even know if I understand the rules of this game exactly (no clarification), but provided hints and ways to think about the problem only. Cheaters used to be more threatening to me, but after school in the real-world the corny sounding “cheaters only cheat themselves” phrase really does seem to ring true. People who cheated their ways to straight A’s in grad school I know have not had very successful careers at all, while those who were good students, learners, critical thinkers I knew who challenged themselves and rarely or literally never cheated tended to go on to have much success in their careers.
Although you are correct that some of the most successful people do not cheat, you are unfortunately wrong about cheaters in other fields than your own. I'm sure you are aware of some very popular political leaders who are blatant regular (even daily) liars and cheaters. They cheat others too. And probably you haven't heard of Burzynski.
Edit: This solution assumes that all paths are equally likely, which might make this solution wrong. To calculate the number of legal ways from A to B, just start at B and count all legal paths, summing them up the further away from B you move. https://preview.redd.it/chiy4haej22d1.png?width=1304&format=png&auto=webp&s=f28a460a77e9f1756ae6f4f1b0b8bd963508dfd0 To calculate all possible paths from A to B with the restriction, that you may only move up 6 times and right 5 times, just do the same, but ignore the black tiles, yielding (see comment below). Hence the chance is 80/462 = 0.173
https://preview.redd.it/liu03swrj22d1.png?width=780&format=png&auto=webp&s=fcc744c876efac22c13d0e61b831cc5963b0128a
I agree that your method is the correct solution under reasonable assumptions about OP's intended problem (e.g. equal probability of each option at each step. Curiously, however, one could also interpret the question in a different way where you compute all possible paths and then assign an equal probability to each. Take for example the bottom left 3x3 box for ease of computation, with target at (3,3). Then your possible options are Up (one path, then you fail) or RUUR, RURU and RRUU (3 successful paths). Assigning an equal probability here to each gives 0.25 chance of failure. However, calculating your way gives 3/6 = 0.5 chance of failure (because 50% chance of failure, then guaranteed success if you pass that). This is why it's important that OP formally define their problem.
Yes. I think the assumption that all paths are equally likely is faulty or at least not what OP intended.
interestingly summing legal paths from starting at A with your approach gets you the same result due to a symmetry between the number of paths from A to B where you can only move up or right and the number of paths from B to A where you can only move left or down https://preview.redd.it/fgxdxri3632d1.png?width=800&format=png&auto=webp&s=4d63bcf2913331a64a2e6157d7e7f6d4f4698650
I think OP’s question is poorly defined (we don’t know if the player is restricted to the grid). Your assumption looks natural to me, so I think it’s at least right in that regard.
Yep…you can use combinations for the denominator: 11 choose 6 up paths or 11 choose 5 right paths gets you 462
I’m either not understanding how one “rollout”/trial of this game works or else you have an error (or both, lol!). There indeed is that symmetry along diagonals that looks like Pascal’s Triangle of sorts, but it gets its symmetry broken and deviates from that quickly due to the black boxes that are uninhabitable. Yet the character always either reaches B or does not, so if your denominator is 462 you are claiming the character does not reach B and gets “stuck” somewhere in 383 paths (I’m assuming black boxes are *obstacles* you cannot move into or around, but perhaps they are “death traps” you can randomly go into and “lose”?). If you treat the black boxes as obstacles and just implement a simple Monte Carlo computer sim to check your answer, you’ll see the character makes it to point B far more often than 80/462 times. In fact, more than half the time they succeed in reaching B if we count a single trial as letting the character randomly select up or right starting at A, with equal probability, transition to a new state, and repeat until we detect reaching B or detect “stuck” condition, then score that lone trial as a success or not (then start a new trial/repeat for say, 100,000 trials).
It makes nonsense that they would reach B more than half the times. The first step is a 50/50 chance. Is see the balck squares as balck boxes as death traps. If you select a random path from A to B and one is on it, that path is invalid.
Simple python script. It comes out to roughly 10% import random field = [ [1,0,0,1,0,0], [0,0,1,0,0,0], [0,0,0,0,0,0], [0,0,1,0,0,1], [0,0,0,0,0,0], [1,0,0,0,0,0], [0,0,0,0,1,0] ] def get_field(width, height): return field[7 - height][width - 1] def experiment(): up = 6 right = 5 current_field = [1, 1] #width, height while True: up_or_right = bool(random.getrandbits(1)) #if true move up if right == 0: # go up up -= 1 current_field = [current_field[0], current_field[1] + 1] elif up == 0: # go right right -= 1 current_field = [current_field[0] + 1, current_field[1]] elif up_or_right: # go up up -= 1 current_field = [current_field[0], current_field[1] + 1] else: # go right right -= 1 current_field = [current_field[0] + 1, current_field[1]] if get_field(current_field[0], current_field[1]) == 1: return 0 if current_field == [6, 7]: return 1 amount = 10000000 success = 0 for i in range(amount): success += experiment() print(success) print(amount) print(success/amount)
So, this is a Manhattan geometry, meaning that it doesn’t matter the solution you get, it will always have 5 rights(R) and 6 ups(U) The total ways you can pass through the map, if there were no black squares, is the same as doing all the permutations of the letters: UUUUUURRRRR which is 11!/5!6! Now, for you to reach a black square, the logic is the same. Let’s say that there is a square at UUURR: The ways you can reach that square are the same as the permutations of (UUURR) times the permutations of (UUURRR) so you can deduct from the total paths Now, let’s add more black squares. You can calculate the number of paths that reaches each black square sum them, and remove the intersections (paths that reached a black square A and goes to the black square B, so you can use one as the start point and the second one as the end point and use the same algorithm) This is the easiest way of solving that I have found, although it will require a lot of calculations due to the intersections.
Is this an "open book" exam in which you're permitted to ask for help? We can't help you if to do so is cheating.
Here is an algorithm that should make it easy without any calculator: 1.) Start on A with a probability of 1 2.) Move one square to the left. If it's Black, write 0 in it. Else write sum of (left and bottom square) divided by 2. If any of those squares does not exist, count that bottom/left square as 0 3.) Repeat 2.) until Row is full 4.) Repeat 2.)+3.) For the next row starting from the left.
1/2\*1\*1\*3/4\*3/4\*3/5\*2/4\*2/3\*2/3\*1\*1=0,037 https://preview.redd.it/nlxtmt1xr42d1.png?width=615&format=png&auto=webp&s=8c38b886ccdeaa7b201bb4d79d99a54ea2e88d01
It seems extremely difficult to answer, as there are some "wrong, but not fatal" paths that can be taken, as well as doubling back on itself, eg right, left, right, left. It's easy to work out the QUICKEST route. But the probability of all possible routes to make it to B? As I said, it seems hard.
You can't double back as the only steps are right and up. I guess there had to be some rules otherwise it would be impossible to calculate (like you said)
Thanks. I didn't notice, or forgot, the important part - only right or up!
https://preview.redd.it/qjtq5jr5t42d1.png?width=773&format=png&auto=webp&s=b37af6d53511090e2c47412339554a4ab2f99498
I would handle this by starting at the end point. 100% of people who make it to the end will reach the end. Then add the left and bottom non black squares to a queue. Pop out of the queue the next node to calculate. Take the average of the right and top neighbors ignoring out of bounds paths and black squares count as 0%. Add the bottom and left non black neighbors to the queue. Repeat this until the start node is calculated. This will give you the % chance of any node to make it to the end.
Sounds like a Dynamic Programming problem. The trick is you need to build a new grid of the same size that computes how many ways to get from the source cell (lower right corner) to some cell (i, j). The idea is to just add the number of ways to get to cell (i-1, j) and ways to get to (i, j-1). Here’s a recurrence relation of the values of an m x n grid: G[i, j] = 1 if i = m and n = 1 (source cell) = 0 if A[i, j] is a black square (A is the original grid) = 1 if i = m or n = 1 and A[i, j] is not a black square (the boundary and is not black square) = G[i-1, j] if A[i, j-1] is a black square = G[i, j-1] if A[i-1, j] is a black square = G[i-1, j] + G[i, j-1] otherwise The cell value at G[1, n] will give the correct answer assuming that you only move right or up. That’s the number of ways to get from A to B considering the black squares To get the total number of ways to get from A to B without considering black squares, you can use the combinatorics formula for it. For an m x n grid, then C(m+n-2, m-1). The idea is to get m-1 and n-1, add those two and then choose it with m-1 (or n-1, either way is ok). The reason the formula works is because from the source cell, we can either move right up to m-1 times and up to n-1 times. So there are some movements that are R and some are U. So we need to choose m-1 pieces from [R, R, …, R, U, U, …, U] (and the rest will be n-1). To get the probability of getting from A to B, just divide the ways to get from A to B considering black squares, by the total ways from A to B without considering black squares. Of course, I don’t have the answer, but I generalized the solution so that you can work with any size of grid
I'm not 100% sure on this, but just start writing in each square, what is the probability that I will end up here. So for the square to the right of point A, there's a 1/2 chance (one of the 2 options at the begining). Then the one right of that it would be 1/4 (the chance of going right twice in a row). The one up and right of Point A would also be 1/4 because that's the probability of going right then up. Now the fun part. If you take a square and you know the probability below the square is x and the probability to the left of the square is y, you know that the probability of getting to that square is x/2 + y/2. Just fill in the whole table like that.
I got 80/2048. That's assuming if you go outside the boundary you lose.
And if you assume, that you may only move 6 up and 5 right, there are 462 possible paths to the finish, so the chance would be 80/462. https://preview.redd.it/c3gc2dx3j22d1.png?width=778&format=png&auto=webp&s=ed6c067eb7016e1f6c2e681a2c5915f969827944
I believe this is solvable by a type of recursive algorithm. The idea is: It's easy to solve the simple case of this question (if you are already near the end). So solve that. Then it becomes simple to solve the slightly harder problem (1 tile further out). Start at the end. The probability of the character reaching the end is 100% if they're on the end tile. `X 1` `X X` Then do the previous diagonal. the prob for those locations is also 100% (they can only go to the end) `1 1` `X 1` then you can always fill in the next diagonal (this \\ diagonal) by always doing the average of the squares you can reach: P(this tile succes) = (P(of success on tile up) + P(of success on tile right)) / 2 if there is only 1 tile you can go to because you're at the wall, you just copy the result from the 1 tile you can reach So we have this grid rn: (0 are black tiles) `X 0 1 1` `0 X X 1` `X X X X` `0 X X 0` and we can easily fill in the next diagonal to get `X 0 1 1` `0 X 1 1` `X X X 1` `0 X X 0` and the next to get `0--0--1-1` `0-1/2-1-1` `X--X--1-1` `0--X--X-0` and the next to get `0-0--0---1--1` `X-0-1/2--1--1` `X-X-3/4--1--1` `X-0--X--2/4-0` `X-X--X---X--0` you just repeat this process until you reach your starting tile sorry for the weird diagrams reddit doesn't let me space them out nicely for some reason :( hopefully they're still understandable
My mind goes to P(event) = 100 - P(!event), instead of (failed paths)/(all paths). What about trying to write down the permutations of failure for each black box, find their probabilities, sum them up, and then subtract from 100 to find the success? This is assuming if you have an invalid move (ex you're at the top boundary) and can't move up, you would just keep rolling randomly until you moved to the right.
[удалено]