Ongelmaketju - ratkaise & esitä ★ Toimittajan suosikki

[Tauko]

Nyt ok ?

Koodi: Valitse kaikki

# Dynamic Programming computation for the difference
# d = #(11) - #(10) across all binary strings of length n

def counts_by_sign(n):
    """
    Compute how many n-bit strings have:
    - more '11' pairs than '10' pairs
    - more '10' pairs than '11' pairs
    - equal numbers of both
    using dynamic programming (DP).
    """
    maxdiff = n - 1                 # Maximum possible difference (in absolute value)
    size = 2 * maxdiff + 1          # Array length to store possible diff values from -maxdiff..+maxdiff
    offset = maxdiff                # Index shift to handle negative differences

    # dp_last[last_bit][diff_index] = number of strings of current length
    dp_last = [[0] * size for _ in range(2)]

    # Initialization: one-bit strings (no pairs yet → diff = 0)
    dp_last[0][offset] = 1          # string "0"
    dp_last[1][offset] = 1          # string "1"

    # Build up to length n
    for pos in range(1, n):
        dp_new = [[0] * size for _ in range(2)]
        for last in (0, 1):         # previous bit: 0 or 1
            arr = dp_last[last]
            for idx, val in enumerate(arr):
                if val == 0:
                    continue
                d = idx - offset     # actual diff value corresponding to this index

                # Transition to new bit = 0
                # If we go 1→0, the diff decreases by 1; otherwise no change
                newd0 = d + (-1 if last == 1 else 0)
                dp_new[0][newd0 + offset] += val

                # Transition to new bit = 1
                # If we go 1→1, the diff increases by 1; otherwise no change
                newd1 = d + (+1 if last == 1 else 0)
                dp_new[1][newd1 + offset] += val
        dp_last = dp_new            # move to next step

    # Final counts for d>0, d<0, d=0
    more11 = more10 = equal = 0
    for last in (0, 1):
        arr = dp_last[last]
        for idx, val in enumerate(arr):
            if val == 0:
                continue
            d = idx - offset
            if d > 0:
                more11 += val
            elif d < 0:
                more10 += val
            else:
                equal += val

    return more11, more10, equal


# Example: compute results for n = 100
n = 100
more11, more10, equal = counts_by_sign(n)
total = 2 ** n

# Display results
print(f"n = {n}")
print(f"Total strings: {total:e}")
print(f"More '11' than '10' : {more11} ({more11 / total:.6%})")
print(f"More '10' than '11' : {more10} ({more10 / total:.6%})")
print(f"Equal number         : {equal} ({equal / total:.6%})")

Tuossa vielä n=100 heittojen jakauma

[JMe1]

Tuossa vielä n=100 heittojen jakauma

No mitenkä tuota nyt sitten tulkitaan ? Kertooko se sen ovatko 11 ja 10 jakaumien huiput kohdakkain ?

[Tauko]

Tuossa vielä n=100 heittojen jakauma

No mitenkä tuota nyt sitten tulkitaan ? Kertooko se sen ovatko 11 ja 10 jakaumien huiput kohdakkain ?

Mitkä 11 ja 10?
Tuo on kaikkien 100 heittojen jakauma.

[JMe1]

Mitkä 11 ja 10?

Jos piirretään kaksi erillistä jakaumaa, toinen sekvenssille 11 ja toinen 10:lle, ja ne sijoitetaan "päällekkäin", pitäsi näkyä vaihesiirto. Ainakaan ne eivät saisi olla identtiset.

[Tauko]

Mitkä 11 ja 10?

Jos piirretään kaksi erillistä jakaumaa, toinen sekvenssille 11 ja toinen 10:lle, ja ne sijoitetaan "päällekkäin", pitäsi näkyä vaihesiirto. Ainakaan ne eivät saisi olla identtiset.

Tarkoitatko, että tehdään jakauma kaikki 10 kolikon heitot, ja sitten jakauma kaikki 11 kolikonheitot. Ja niitä kahta jakaumaa verrataan?

Tuo laittamani jakauma ei siihen vastaa, vaan on pelkästään kaikkien 100 kolikon heitot jakauma.

Tuntuma kyllä on, että mitä suurempi määrä kolikon heittoja sarjassa on, tuhat, miljoona...., niin sitä lähempänä HH ja HT suhde on 50:50.

[JMe1]

Tarkoitatko, että tehdään jakauma kaikki 10 kolikon heitot, ja sitten jakauma kaikki 11 kolikonheitot. Ja niitä kahta jakaumaa verrataan?

Juuri näin. Mutta kun viittasin tekemääni testiin 100 vs 102 heittoa, voi olla että käyristä ei ole mahdollista nähdä eroa.

[Tauko]

Tarkoitatko, että tehdään jakauma kaikki 10 kolikon heitot, ja sitten jakauma kaikki 11 kolikonheitot. Ja niitä kahta jakaumaa verrataan?

Juuri näin. Mutta kun viittasin tekemääni testiin 100 vs 102 heittoa, voi olla että käyristä ei ole mahdollista nähdä eroa.

[JMe1]

Tarkoitatko, että tehdään jakauma kaikki 10 kolikon heitot, ja sitten jakauma kaikki 11 kolikonheitot. Ja niitä kahta jakaumaa verrataan?

Sorry, ilmaisin itseäni epäselvästi. Lukemalla 10 en tarkoittanut kymmentä heittokertaa vaan kombinaatiota HT. Laiskuuttani koodasin tyyliin '1' = H ja '0' = T.

Heitetään kolikkoa niin kauan että HT (minun merkinnällä 10) ilmenee 25 kertaa. Toistetaan monta kertaa jotta saadaan piirrettyä jakauma. Oletan sen olevan Gaussin käyrän näköinen.

Tehdään samanlainen Gaussin käyrä HH:lle. Tämän jälkeen käyrät piirretään samaan kuvaajaan. Ne menevät (oletan) lähes päällekkäin, mutta joitakin eroja pitäisi olla.

Nyt kun voittomäärä korvataan rajoituksella heittomäärään siellä sadan heiton tuntumassa, se tarkoittaa että piirrämme pystyviivan kohdalle 100 ja alamme siirtää sitä vasemmalle. Huomaamme että se syö käyristä erikokoiset pinta-ala- lohkot. Ja tämä on mielestäni syy siihen että HT voittaa alkuperäismäärittelyn mukaisen kisan.

[Tauko]

Tarkoitatko, että tehdään jakauma kaikki 10 kolikon heitot, ja sitten jakauma kaikki 11 kolikonheitot. Ja niitä kahta jakaumaa verrataan?

Sorry, ilmaisin itseäni epäselvästi. Lukemalla 10 en tarkoittanut kymmentä heittokertaa vaan kombinaatiota HT. Laiskuuttani koodasin tyyliin '1' = H ja '0' = T.

Heitetään kolikkoa niin kauan että HT (minun merkinnällä 10) ilmenee 25 kertaa. Toistetaan monta kertaa jotta saadaan piirrettyä jakauma. Oletan sen olevan Gaussin käyrän näköinen.

Tehdään samanlainen Gaussin käyrä HH:lle. Tämän jälkeen käyrät piirretään samaan kuvaajaan. Ne menevät (oletan) lähes päällekkäin, mutta joitakin eroja pitäisi olla.

Nyt kun voittomäärä korvataan rajoituksella heittomäärään siellä sadan heiton tuntumassa, se tarkoittaa että piirrämme pystyviivan kohdalle 100 ja alamme siirtää sitä vasemmalle. Huomaamme että se syö käyristä erikokoiset pinta-ala- lohkot. Ja tämä on mielestäni syy siihen että HT voittaa alkuperäismäärittelyn mukaisen kisan.

Ok ei ongelmaa itsekin käytin merkintää 11 ja 10 laskennassa, mutta tuossa sekosin, että tarkoittaisit heittokierroksien lukumäärää. Minun moka.

Mutta vielä hämmentää tämä:
"Heitetään kolikkoa niin kauan että HT (minun merkinnällä 10) ilmenee 25 kertaa."
- kyseessä lienee simulaatio arpomalla ja katsotaan miten jakauma kehittyy ja tarkentuu toistojen lisääntyessä.

Tuossa 10 heiton ja 11 heiton pituisten heittojonojen sarjoissa, jotka laitoin, on kaikki 1024 ja 2048 eri variaatiot, ei simulointia ei satunnaisuutta tuloksessa.

Samoin siinä 100 lantin heitossa tarkka jakauma, ei estimaatti.

[JMe1]

kyseessä lienee simulaatio arpomalla ja katsotaan miten jakauma kehittyy ja tarkentuu toistojen lisääntyessä.

Kyllä. En keksinyt muuta tapaa luoda kuvaaja jakaumalle.

[JMe1]

YouTubesta löydetty:
"Mahdoton" logiikkapulma

Juhlissa on 100 ihmistä, jotka ovat joko valehtelijoita tai totuudenpuhujia. Valehtelijat valehtelevat aina, ja totuudenpuhujat puhuvat aina totta.
Juhlien jälkeen kysyt jokaiselta henkilöltä: "Kuinka montaa totuudenpuhujaa kättelit?"
Jokainen henkilö antoi eri vastauksen, joka vaihteli 0:sta 99:ään (vastaukset olivat 0, 1, 2, ..., 98, 99).
Kuinka monta valehtelijaa oli juhlissa?

[Ykkösnolla]

Pari varmennusta:
1. Kättelihän jokainen jokaista?
2. Tietäväthän toisistaan, onko toinen (se jota kättelee) valehtelija vai todenpuhuja?

[JMe1]

Pari varmennusta:
1. Kättelihän jokainen jokaista?
2. Tietäväthän toisistaan, onko toinen (se jota kättelee) valehtelija vai todenpuhuja?

1. Ei tiedetä.
2. Totuudenpuhuja tietää siltä osin kun on väittänyt kätelleensä N totuudenpuhujaa.

Ja huomaa että tehtävä on YouTube kanavalta, eli tehtävänmäärittely on eksakti. Mitään tarkennuksia ei pitäisi tarvita.

[POPE]

YouTubesta löydetty:
"Mahdoton" logiikkapulma

Juhlissa on 100 ihmistä, jotka ovat joko valehtelijoita tai totuudenpuhujia. Valehtelijat valehtelevat aina, ja totuudenpuhujat puhuvat aina totta.
Juhlien jälkeen kysyt jokaiselta henkilöltä: "Kuinka montaa totuudenpuhujaa kättelit?"
Jokainen henkilö antoi eri vastauksen, joka vaihteli 0:sta 99:ään (vastaukset olivat 0, 1, 2, ..., 98, 99).
Kuinka monta valehtelijaa oli juhlissa?

Jos kaikki kättelivät toisiaan, niin kaikki sata olivat valehtelijoita.

[Ykkösnolla]

Pari varmennusta:
1. Kättelihän jokainen jokaista?
2. Tietäväthän toisistaan, onko toinen (se jota kättelee) valehtelija vai todenpuhuja?

1. Ei tiedetä.
2. Totuudenpuhuja tietää siltä osin kun on väittänyt kätelleensä N totuudenpuhujaa.

Ja huomaa että tehtävä on YouTube kanavalta, eli tehtävänmäärittely on eksakti. Mitään tarkennuksia ei pitäisi tarvita.

No sitten: 99 valehtelijaa ja 1 todenpuhuja ja kukaan ei kätellyt ketään

(Todenpuhuja vastaa 0 ja valehtelijoille riittää vaihtoehtoja.)