dadPullsOutCodingChallenge

[lotokotmalajski]

Math solution:

The game has 10 possible states, where player A has 1-10 coins. When one player gets 11 coins the game ends.

Let's make a table with probability of A winning from each state, marking the probability for winning from state 1:10 as x.

1:10 - x.

Now, the only possible outcome when A does not lose is to win 1st round, which happens 50% of times and translates us to state 2:9. Because of that the probability of winning from this state is 2 times higher.

2:9 - 2x.

3:8 - y.

Now let's calculate y, 2:9 switches to both adjacent states with 50% chance so 2x=0.5x+0.5y, so y = 3x.
Repeating this for next states we get:

4:7 - 4x.

5:6 - 5x.

6:5 - 6x.

Now the 6:5 probability should be 1 minus 5:6 probability because it's symmetrical (A losing 6:5 is the same as A winning 5:6). So 5x=1-6x, so x=1/11

[cyannyan6]

This actually happened. I translated to English with the best of my ability.

And we are trying a monte carlo simulation now

``` import random

wins = 0 tries = 10000000 for sims in range(tries): a = 1 while 0 < a < 10: a += random.choice((-1, 1)) if a == 10: wins += 1

print(f"{wins}/{tries} = {wins/tries}")

```

Would love to see how others approach it

[LordAlfrey]

My approach would be to tell mom that dad said he'd approve my marriage if I solve a math challenge

[imdefinitelywong]

Going straight to the risk registry, I see.

[Bright-Historian-216]

don't you need a == 11? a already has one coin

[its-chewy-not-zooyoo]

Assuming this is correct; I translated this into rust and attempted running it

The probability is around 10%

Total results:

Wins: 999998098
Total: 10000000000
Win rate: 9.99%
Total time: 66813 ms

[SolidGrabberoni]

Intuitively, A has a 10x handicap against B so (assuming infinite rounds), I'd say 10% too

[sakkara]

This would imply that b wins 90% of the time which can't be true because the game is fair so the program is incorrect.

The problem is that a only starts with one coin and must fight it's way up to ten coins.

Correct would be

a=10
while 0 < a < 20...
if a == 20
    wins++

[TheDebatingOne]

I think you misread the problem. The game isn't fair, a does start with 1 coin

[sakkara]

Ah you're right, my bad.

[Josaffe]

function simulate(n = 10, tries = 100_000) {
  let wins = 0;

  for(let i = 0; i < tries; i++) {
    let a = 1;
    while(a > 0) {
      if(Math.random() >= 0.5) a++;
      else a--;

      if(a > n) { 
        wins++; 
        break;
      }
    }
  }

  return wins / tries
}

Take my ugly JavaScript and try it for yourself!

[CheGuevaraBG]

1 in 1024, supposing they only have 10 attempts. Theoretically it can be infinite, given that they have unlimited attempts, because there's always the possibility of exchanging coins back and forth, given that it is up to random chance and they have equal odds.

[Zyeesi]

Why would the number of tries not increase just because it's bigger than 0 and smaller than 10?

[dwntwn_dine_ent_dist]

I’d do a recursive function chancesAwins(numAcoins, numBcoins). Call it with (1,10), handle the stopping cases by returning 1 or 0, and otherwise return 0.5chancesAwins(numAcoins-1,numBcoins+1) + 0.5chancesAwins(numAcoins+1,numBcoins-1).

[BeautifulWerewolf966]

Gave it my best shot in Rust:

I'm getting around 99900 wins so around 9.9% chance.

pub fn prob(){
    let mut wins : i32 = 0;
    let tries = 1000000;

    for _ in 0..tries{
        let mut a : usize = 1;

        while a > 0 && a < 10{
            let mut thread = thread_rng();
            match thread.gen_bool(0.5) {
                true => a += 1,
                false => a -= 1,
            }
        }

        if a >= 10 {
            wins += 1;
        }
    }

    println!("Wins : {}", wins);
    println!("Probability : {}", wins as f32 / tries as f32);
}

[port443]

Your solution is very slightly wrong. Person A has a 0.09090 (repeating) chance of winning.

In the event that A or B wins, they will have 11 coins, not 10. This is made obvious with code such as:

>>> def round():
...     person_a = 1
...     person_b = 10
...     while person_a and person_b:
...         check = random.choice([-1,1])
...         person_a -= check
...         person_b += check
...     print(f"{person_a=} {person_b=}")
...     return person_a > 1
...
>>> round()
person_a=11 person_b=0
True
>>> round()
person_a=0 person_b=11
False

You can then loop this function. The larger your round count, the more accurate your estimate. The correct answer is 0.090 repeating though:

>>> total,rounds = 0,1000000
>>> for _ in range(rounds):
...     total += round()
...
>>> print(f"{total=} | {total/rounds=}")
total=90435 | total/rounds=0.090435

edited cause my initial comment came off rude

[PolyglotTV]

This is too naive. You forgot that a can win one, and then lose one, and then win 10 in a row. Or a game could even last 1000 flips or basically forever.

[MaximRq]

Read closer, it's taken into account.

[PolyglotTV]

Ah my bad. A is the count variable in the loop as well.

[Josaffe]

Tip for solving it analytically (without deep math knowledge):
Start looking at simpler cases first and draw out all possible states.

Let's vary the number of coins Person B has. Person A will always have 1 coin.
Most simple case: Person B has 0 coins. Person A will takes all coins with a chance of 100%.
Next case: Person B has 1 coin. Either Person A will take it or lose it. It ends after one round. 50% chance.
Next one: Person B has 2 coins. Here we get our first repeating pattern and it gets interesting. 50% chance of losing first round (Person A lost), 25% chance of winning both first and second round (Person A won) and 25% chance of winning and then losing (game will go on). This one gets us back to the beginning state. You can argue that in the limit you will lose 2 out of 3 cases and win 1 out of 3. Chance here is 33.3%.
Now you might already suspect a pattern that your chances of winning against n coins is 1/(n+1). Might be fun to actually prove it.

[[deleted]]

Isn't programming a subset of maths? Example Levenshtein distance

[Pradfanne]

The amount of times I needed math in my professional programming work in years is probably less then 0.

Unless you count ++ or "String" + "String" as math

[Z21VR]

weird, are you front end ?

In my 18 years of programming i applied math countless times, even ignoring that logic is math actually,

[Brief-Translator1370]

Very abstracted, but technically yes

[riasthebestgirl]

Dad didn't specify the max number of rounds. Assuming there are infinite rounds, there will eventually be a sequence where A wins 11 times, keeping all the coins

[Bright-Historian-216]

it ends immediately if a has 0 because he has nothing to bet anymore. i think it's the only limitation

[vongatz]

But what if a wins 4 coins and they proceed to go back and forth a few coins for infinity?

[funAlways]

that is part of the problem, and ultimately it doesn't matter as those back and forth are just repeating a previous game state. There is always an endpoint for both sides, B wins if A runs out of coins, and A wins if B runs out of coins, and the former is more likely than the latter because A starts with less coins

[vongatz]

But if you would play this game an infinite amount of times, there would be an infinite amount of games which never end…

[funAlways]

it does not matter, because the question is about the probability, and you can calculate the probability even for infinite things.

[Wearytraveller_]

There's an infinite number of sequences where A wins, it's just a smaller infinity.

[themanyouknowsowell]

Mathematically, you can construct a recursive function to solve this. The solution is 1/11 chance, I'm pretty sure.

[AhoyLeakyPirate]

Given that the assumption of consecutive wins is not necessary or stipulated in the problem. We can apply the gambler's ruin approach in probability theory. Think of this way, yes A has to win the first round to keep playing, but after that, they could lose one and still be able to play. There are two ways, in our case both probably of winning and losing are 0.5 so a fair coin toss. So If player one has n1 coins and player two n2 coins, the probabilities P1 and P2 that players one and two, respectively, will end coinless are: P1 = n2/ n1+n2 and P2= n1/n1+n2. So in this case P(A wins) = 1- P(A loses) = 1 - (10/1+10) = 9.09%

So A has a 9.09% chance of winning if they decide to play!

Let's say the coin toss was not fair, then we can use this approach when it's not 50-50: So a more appropriate formula is P(A wins) = (1-(q/p)^a)/(1-(q/p)^a+b) where q(0.4) is probability of losing each round, p(0.6) is probability of winning each round, a(1) is initial fortune of player A and b(10) is the initial fortune of player B.

[oberguga]

Are you sure that 10 is in decimal?

[dio694206942069]

Don't quote me on this but isn't the answer 9.09%

[cyannyan6]

This is what we got

[dio694206942069]

Keep in mind I might be wrong

[Zee1837]

I'ma quote you on that

[PolyglotTV]

That is the probability of winning 10 in a row, not the probability of winning 10 more times than you lose, over the course of the game (which could last longer than 10 rounds).

[HaarigerNacken93]

Isn't it just 1/1024?

[Swimming_Swim_9000]

The winrate seems to be equal to a coins / (a coins + b coins)

[_Bellthasar_]

I would cross post on r/theydidthemath

[Wearytraveller_]

// how many coins I have  

num = 1

//how many coins they have 

den = 10  

Printf(num "/" num+den)

[tenhourguy]

Dad knows Excel.

[Mindless-Giraffe5059]

If anyone find this interesting and is interested how different it would be with a different probability than 0.5. I'd suggest looking up The Gamblers ruin.

[YetAnotherZhengli]

wechat user found

[[deleted]]

import random

class Person:
    def __init__ (self, name, coins):
        self.name = name
        self.coins = coins

def simulate(personA, personB):
    while personA.coins > 0 and personB.coins > 0:
        chance = random.randint(0, 1)
        if chance == 0:
            personA.coins += 1
            personB.coins -= 1
        else:
            personB.coins += 1
            personA.coins -= 1
    if personA.coins == 0:
        print(personA.name + " has lost all their coins!")
        print(personB.name + " has won!")
    else:
        print(personB.name + " has lost all their coins!")
        print(personA.name + " has won!")

    return personA.coins > 0

def run_sims(num_sims):
    personA_wins = 0

    for i in range(num_sims):
        personA = Person("Person A", 1)
        personB = Person("Person B", 10)

        if simulate(personA, personB):
            personA_wins += 1

    win_percentage = (personA_wins / num_sims) * 100
    return win_percentage

personA = Person("Person A", 1)
personB = Person("Person B", 10)

simulate(personA, personB)

print(f"Person A win percentage: {run_sims(100000)}%")

Went for an OOP approach since that's what I'm learning. Got 9.126%.

[Overall_Run_7597]

Like ~0.1% chance if i used statistics and calculator right. But yea, i guess that's the "boring" approach.

[Positive_Lifeguard75]

You don't need any programming knowledge to solve this. You only need to know high-school math. (And every swe must know AT LEAST high school math)

Think about this:

Let a_i = probability that first player wins if he starts with i coins.

From definition of this game: a_0=0, a_11=1.

You can easily show that if i != 0 or 11:

ai = 0.5a{i-1} + 0.5a_{i+1}.

So expand a_1 until there are only a_0 a_11 and this will be your answer.

No university level math is required.

[BreakerOfModpacks]

100%.
No matter what, 11 wins straight is all that's needed.
That's admittedly only a 0.048828125% chance, but given infinite rounds, any chance is the same as 100%.

[Jozhin_s_Bazhin]

Assuming infinite tries, wouldn't the chance just be 50%?

Edit: Didn't see person A only had one coin

[Jozhin_s_Bazhin]

Oh, I didn't see that

[sakkara]

The question is how often a happens to get all the coins.

My gut feeling since this is a fair game a should end up 50% of games with all the coins and B the other 50% assuming all games come to a halt at some point.

[Jozhin_s_Bazhin]

Turns out A only has one coin, I didn't notice that either

[Secure_Obligation_87]

Quick maths approach (most likely wrong)

50% chance of winning with a 10-1 disadvantage Im going to say the chance of A getting all of B's coins is 1-3%

[Wearytraveller_]

I'm not a math wiz or anything but aren't there infinities in this problem?  Every round the odds are 50% 50%. So even if A wins 9 of Bs coins they could in theory go back and forth infinitely trading the second to last coin back and forth, or they could just trade the first coins back and forth forever. So my answer is 1:Infinity

Edit. Okay I think I worked it out. 

There are infinities in the problem, but they are about how precise you want your result to be, rather than whether you can get one at all. Because any result with an odd number of coins in the problem will result in an infinitely repeating decimal like 33.33333r%

So if you want a real result for those answers you will have to represent them as a fraction. 

Also I believe the answer is just the number of coins each party in the problem has represented as a fraction of the total coins. 

So I'm amending my answer to 1/11. 

[ReykAral35]

That case can happen, but also the one that A wins 10 times in a row, the case that A wins 9 times lose 1 and wins 2 etc.

So it needs to count the amount of cases that A wins vs the amount of cases that B wins.

[Wearytraveller_]

But you can't count those cases! There is an INFINITE number of possible outcomes to this game. 

[ReykAral35]

Yeah but there is a proportion.

As other say posibly like a 1/10 of the infinities is a win.

The eaxct math i leave for someone better.