12
\$\begingroup\$

Imagine an infinite symmetrical triangle of pegs, where the rows have size 1, 2, 3, ... (similar to Pascal's Triangle). All the pegs are red apart from k (your input), which are blue. A ball is then dropped from the top. Each time it hits a peg it has an equal chance to bounce left or right, moving to the peg directly left or right in the row below.

The ball's value starts at 1. Every time the ball hits a blue peg, add its value to your earnings and then double its value. Every time it hits a red peg, reset the value to 1 and earn nothing.

What is the highest expected value you can achieve by placing k blue pegs? Give your answer as a ratio, a floating point number, or a numerator over 2^(k-1).

This is code-golf, so the shortest answer wins.

Test Cases:

1 -> 1 2 -> 2 1 1 0 3 -> 13/4 1 1 0 0 1 0 4 -> 5 1 1 1 0 1 0 5 -> 57/8 1 1 1 0 1 0 0 1 0 0 6 -> 151/16 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 7 -> 27/2 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 8 -> 143/8 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 9 -> 717/32 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 10 -> 31 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 11 -> 5103/128 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 12 -> 12511/256 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 13 -> 2127/32 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 14 -> 1349/16 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 15 -> 103 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 
\$\endgroup\$
2
  • 4
    \$\begingroup\$ By "expected" it seems you mean the average over all possible outcomes, not the single highest possible outcome (which would be achieved by hitting all blue pegs.) It looks like the strategy is to fill the central columns but it is not clear if this continues at high k. \$\endgroup\$ Commented Jan 11 at 7:20
  • 1
    \$\begingroup\$ Interesting; k=18 is like k=15: 12122222121. \$\endgroup\$ Commented Jan 13 at 12:27

3 Answers 3

5
\$\begingroup\$

JavaScript (ES6), 129 bytes

Returns a floating point number.

This assumes that the best score is always achieved by putting either 1 or 2 blue pegs as close as possible to the central column.

f=(n,m,r)=>m>>n?r:f(n,-~m,(g=(x,v=1,y=0,b=n,q=m>>y&b>1)=>s=b&&(g(x-=y&1,v=x+q&&x?1:v*2,++y,b+=~q)+g(x+1,v,y,b)+v-v%2)/2)``<r?r:s) 

Try it online!

Full output

You can use this version (less recursive but otherwise identical) to get all answers up to \$n=15\$:

a( 1) = 1 (1/1) a( 2) = 2 (2/1) a( 3) = 3.25 (13/4) a( 4) = 5 (5/1) a( 5) = 7.125 (57/8) a( 6) = 9.4375 (151/16) a( 7) = 13.5 (27/2) a( 8) = 17.875 (143/8) a( 9) = 22.40625 (717/32) a(10) = 31 (31/1) a(11) = 39.8671875 (5103/128) a(12) = 48.87109375 (12511/256) a(13) = 66.46875 (2127/32) a(14) = 84.3125 (1349/16) a(15) = 103 (103/1) 
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 155 bytes

≔⟦⟦⟦⁰⟧⟧⟧θF⊖N«≔⟦⟧ηFθ«⊞ηEκ⎇⁼⊕μLκ⁺λ⟦⊕⌈λ⟧λF§κ±¹⊞η⁺κ⟦⟦λ⟧⟧»≔ηθ»Fθ«≔⟦⟧ηFι«≔⟦⟧ζF⊕⌈Eι⌈λ⊞ζE∨⁺∧η§§η±¹λ∧ζ§ζ±¹⟦⟦¹¦⁰⟧⟧⎇№κλ⁺§μ⁰μ⟦¹§μ¹⟧⊞ηζ»UMηEκ∕ΣEμ⊟ξX²⊕⁺λν⊞υΣ⁺Eη↨κ⁰⊟η»I⌈υ 

Try it online! Link is to verbose version of code. Slow, so can only reach k=10 on TIO. Explanation: Assumes all solutions have the following properties: a) the topmost peg is blue b) all forward diagonals only contain one run of blue pegs c) no blue peg lies below two red pegs.

≔⟦⟦⟦⁰⟧⟧⟧θ 

Start with a blue topmost peg.

F⊖N« 

Repeat for each additional peg.

≔⟦⟧η 

Start building a new list of layouts.

Fθ« 

Loop over the old list of layouts.

⊞ηEκ⎇⁼⊕μLκ⁺λ⟦⊕⌈λ⟧λ 

Create a new layout with a peg appended to the last forward diagonal.

F§κ±¹⊞η⁺κ⟦⟦λ⟧⟧ 

Create layouts with a new forward diagonal starting at each valid position according to property c) above.

»≔ηθ 

Save the new list of layouts.

»Fθ« 

Loop over the list of layouts with k pegs.

≔⟦⟧η 

Start building up an array of ball values and scores.

Fι« 

Loop over each forward diagonal of the layout.

≔⟦⟧ζ 

Start building up a list of ball values and scores for this diagonal.

F⊕⌈Eι⌈λ 

Loop over enough reverse diagonals to cover all possible routes though blue pegs.

⊞ζE∨⁺∧η§§η±¹λ∧ζ§ζ±¹⟦⟦¹¦⁰⟧⟧⎇№κλ⁺§μ⁰μ⟦¹§μ¹⟧ 

For each route to this peg, calculate the new ball value and score, and save those values to the list.

⊞ηζ 

Save the list of ball values and scores to the array.

»UMηEκ∕ΣEμ⊟ξX²⊕⁺λν 

For each peg, calculate half of the expected value of routes that reach the peg, taking the chance of reaching the peg into account.

⊞υΣ⁺Eη↨κ⁰⊟η 

For each peg on the rightmost side of the array, there is a 50% chance of the ball bouncing out of the array, in which case the expected value of balls leaving the array is half of the peg's expected value, and similarly for each peg on the bottom row of the array, except for the bottom rightmost peg, which is simply scored twice. Save the resulting total score for all exits from the array.

»I⌈υ 

Output the maximum possible score.

Additionally assuming that the centre column is only composed of blue pegs (at least as far down as the pegs reach) increases the speed allowing k=14 on TIO. Try it online! Link is to verbose version of code. This version also includes a diagram of the pegs (but using b and r for blue and red instead of 1 and 0).

\$\endgroup\$
0
\$\begingroup\$

Python3, 653 bytes

from itertools import* E=enumerate P=lambda n,k:[0]*int((len(n)-len(k))/2) def f(k): F=[] for i in range(1,k+1): if sum(map(len,t:=[[1]*j for j in range(1,i+1)]))>=k: L=count() D={next(L):(x,y)for x,r in E(t)for y,_ in E(r)} for l in combinations(D,k): T=eval(str(t)) for u in l:X,Y=D[u];T[X][Y]=2 T=[[*map(int,'0'.join(map(str,k)))]for k in T];T=[P(T[-1],k)+k+P(T[-1],k)for k in T] q,R=[(1,0,0,T[0].index(2)if 2 in T[0]else T[0].index(1))],[] for b,e,x,y in q: if x==len(T):R+=[e];continue B,V=[1,b*2][T[x][y]==2],[e,e+b][T[x][y]==2] q+=[(B,V,x+1,y+1),(B,V,x+1,y-1)] F+=[sum(R)/len(R)] return max(F) 

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ F+=[sum(R)/len(R)] can be F+=sum(R)/len(R),. \$\endgroup\$ Commented Jan 12 at 16:43
  • \$\begingroup\$ 578 bytes \$\endgroup\$ Commented Nov 19 at 3:30

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.