Proof that there is no sequences of algorithms A1, A2, …, assigned to each prisoner, giving a winning strategy (assuming a computable warden given indices for the Ak):
Gur jneqra fvzhyngrf N-bar ba mreb mreb mreb… hagvy vg bhgchgf bar be mreb nsgre ernqvat x ovgf bs gur vachg. Gur jneqra gura cynprf gur bgure pbybe ung ba cevfbare 1, jub jvyy sbyybj N-bar naq thrff vapbeerpgyl; gur jneqra rafherf guvf ol cynpvat mreb ba cevfbaref gjb guebhtu x. Gur jneqra ercrngf guvf jvgu N-x+1 naq cevfbare x+1, fb gung x+1 jvyy thrff vapbeerpgyl. Naq fb ba. Fvapr rnpu Nx unygf nsgre ernqvat svavgryl znal ovgf sebz vgf benpyr, gur jneqra pna sbepr na vapbeerpg nafjre jvgu bayl svavgryl znal ovgf. Guvf jnl, gur jneqra pna sbepr vasvavgryl znal vapbeerpg nafjref. (Guvf eryngvivmrf gb nal benpyrf lbh pner gb tvir gb gur cevfbaref, nf ybat nf gur jneqra unf npprff gb gur pbhagnoyr wbva bs gubfr benpyrf.)
Proof that there is no sequences of algorithms A1, A2, …, assigned to each prisoner, giving a winning strategy (assuming a computable warden given indices for the Ak):
Gur jneqra fvzhyngrf N-bar ba mreb mreb mreb… hagvy vg bhgchgf bar be mreb nsgre ernqvat x ovgf bs gur vachg. Gur jneqra gura cynprf gur bgure pbybe ung ba cevfbare 1, jub jvyy sbyybj N-bar naq thrff vapbeerpgyl; gur jneqra rafherf guvf ol cynpvat mreb ba cevfbaref gjb guebhtu x. Gur jneqra ercrngf guvf jvgu N-x+1 naq cevfbare x+1, fb gung x+1 jvyy thrff vapbeerpgyl. Naq fb ba. Fvapr rnpu Nx unygf nsgre ernqvat svavgryl znal ovgf sebz vgf benpyr, gur jneqra pna sbepr na vapbeerpg nafjre jvgu bayl svavgryl znal ovgf. Guvf jnl, gur jneqra pna sbepr vasvavgryl znal vapbeerpg nafjref. (Guvf eryngvivmrf gb nal benpyrf lbh pner gb tvir gb gur cevfbaref, nf ybat nf gur jneqra unf npprff gb gur pbhagnoyr wbva bs gubfr benpyrf.)