Reply to thread

Message

<blockquote data-quote="tbitonti" data-source="post: 1349479" data-attributes="member: 10416">Every other prisoner ...Math geek alert.&nbsp;&nbsp; <img src="https://cdn.jsdelivr.net/joypixels/assets/8.0/png/unicode/64/1f61b.png" class="smilie smilie--emoji" loading="lazy" width="64" height="64" alt=":p" title="Stick out tongue&nbsp; &nbsp; :p"&nbsp; data-smilie="7"data-shortname=":p" /> As an aside, the notes below are really a condensation of doingthe solution by a complete simulation.&nbsp; Even the chart at thebottom is nearly so, as the numbers are a compression of thenumber ranges and offsets.Does anyone know a non-iterative way to solve this using elementaryfunctions (or even using Fibonacci numbers, or a base 2 representationand a summation)?&nbsp; I put a mini-formula at the bottom, but it's justa start.Here are my notes (they read best with a fixed width font):from&nbsp; 1 .. 1000 [by&nbsp; 1] --&gt; take out&nbsp; 1,&nbsp; 3,&nbsp; 5 .. 999 --&gt; leaving&nbsp; 2 .. 1000 [by&nbsp; 2]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [count == 1000]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; [count ==&nbsp; 500]from&nbsp; 2 .. 1000 [by&nbsp; 2] --&gt; take out&nbsp; 2,&nbsp; 6, 10 .. 998 --&gt; leaving&nbsp; 4 .. 1000 [by&nbsp; 4]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [count ==&nbsp; 500]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; [count ==&nbsp; 250]from&nbsp; 4 .. 1000 [by&nbsp; 4] --&gt; take out&nbsp; 4, 12, 20 .. 996 --&gt; leaving&nbsp; 8 .. 1000 [by&nbsp; 8]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [count ==&nbsp; 250]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; [count ==&nbsp; 125]&nbsp; renumber by dividing by 8.from&nbsp; 1 ..&nbsp; 125 [by&nbsp; 1] --&gt; take out&nbsp; 1,&nbsp; 3,&nbsp; 5 .. 125 --&gt; leaving&nbsp; 2 ..&nbsp; 124 [by&nbsp; 2]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [count ==&nbsp; 125]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; [count ==&nbsp;&nbsp; 62]from&nbsp; 2 ..&nbsp; 124 [by&nbsp; 2] --&gt; take out&nbsp; 4,&nbsp; 8, 12 .. 124 --&gt; leaving&nbsp; 2 ..&nbsp; 122 [by&nbsp; 4]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [count ==&nbsp;&nbsp; 62]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; [count ==&nbsp;&nbsp; 31]from&nbsp; 2 ..&nbsp; 122 [by&nbsp; 4] --&gt; take out&nbsp; 6, 14, 22 .. 118 --&gt; leaving&nbsp; 2 ..&nbsp; 122 [by&nbsp; 8]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [count ==&nbsp;&nbsp; 31]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; [count ==&nbsp;&nbsp; 16]from&nbsp; 2 ..&nbsp; 122 [by&nbsp; 8] --&gt; take out&nbsp; 2, 18, 34 .. 114 --&gt; leaving 10 ..&nbsp; 122 [by 16]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [count ==&nbsp;&nbsp; 16]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; [count ==&nbsp;&nbsp; 8]from 10 ..&nbsp; 122 [by 16] --&gt; take out 10, 42, 74 .. 104 --&gt; leaving 26 ..&nbsp; 122 [by 32]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [count ==&nbsp; &nbsp; 8]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; [count ==&nbsp;&nbsp; 4]from 26 ..&nbsp; 122 [by 32] --&gt; take out 26, 90&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; --&gt; leaving 58, 122&nbsp; &nbsp; [by 64]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [count ==&nbsp; &nbsp; 4]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; [count ==&nbsp;&nbsp; 2]from 58, 122&nbsp; &nbsp; [by 64] --&gt; take out 58&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; --&gt; leaving 122&nbsp; &nbsp; &nbsp; &nbsp; [by 128]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [count ==&nbsp; &nbsp; 2]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; [count ==&nbsp;&nbsp; 1]Leaving 122.Backing up: 122 * 8 == 976.&nbsp; The 976'th prisoner is last.Model:Prisoner numbers:&nbsp; &nbsp; a(i) + (k - 1) * 2^i&nbsp; &nbsp; i gives the generation number&nbsp; &nbsp; a(i) is the number of the first prisoner&nbsp; &nbsp; k ranges from 1 .. K(i)&nbsp; &nbsp; K(i) is the number of prisoners remaining&nbsp; &nbsp; a(i) ... (K(i) - 1) * 2^i gives the prisoner number rangeThe initial generation is generation 0, before any prisoners are removed.The initial prisoner number, a(0), is 1.The initial prisoner count, K(0), is 1000.Then:For each generation 'i' there is a parity of '0' or '1', whereparity '0' means that the first prisoner will be removed,and parity '1' means that the second prisoner will be removed. &nbsp; &nbsp; P(i) == 0, 1In the given problem, P(0) == 0.For a given 'i', 'P(i+1)' is given by:&nbsp; &nbsp; P(i+1) = P(i)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; if K(i) is even;&nbsp; &nbsp; P(i+1) = P(i) + 1 (mod 2)&nbsp;&nbsp; if K(i) is odd.For a given 'i', 'a(i+1)' is given by:&nbsp; &nbsp; a(i+1) = a(i) + 2^i&nbsp; &nbsp; &nbsp; &nbsp;&nbsp; if P(i) is 0;&nbsp; &nbsp; a(i+1) = a(i)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; if P(i) is 1.For a given 'i', 'K(i+1)' is given by:&nbsp; &nbsp; K(i+1) = K(i) / 2&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; if K(i) is even;&nbsp; &nbsp; K(i+1) = (K(i) + 1) / 2&nbsp; &nbsp;&nbsp; if K(i) is odd and P(i) is 1;&nbsp; &nbsp; K(i+1) = (K(i) - 1) / 2&nbsp; &nbsp;&nbsp; if K(i) is odd and P(i) is 0.Then:&nbsp; &nbsp;&nbsp; i&nbsp; &nbsp;&nbsp; a(i)&nbsp; &nbsp; P(i)&nbsp; &nbsp; K(i)&nbsp; &nbsp; &nbsp; 2^i&nbsp; &nbsp;&nbsp; 0&nbsp; &nbsp; &nbsp;&nbsp; 1&nbsp; &nbsp; &nbsp;&nbsp; 0&nbsp; &nbsp;&nbsp; 1000&nbsp; &nbsp; &nbsp;&nbsp; 1&nbsp; &nbsp;&nbsp; 1&nbsp; &nbsp; &nbsp;&nbsp; 2&nbsp; &nbsp; &nbsp;&nbsp; 0&nbsp; &nbsp; &nbsp; 500&nbsp; &nbsp; &nbsp;&nbsp; 2&nbsp; &nbsp;&nbsp; 2&nbsp; &nbsp; &nbsp;&nbsp; 4&nbsp; &nbsp; &nbsp;&nbsp; 0&nbsp; &nbsp; &nbsp; 250&nbsp; &nbsp; &nbsp;&nbsp; 4&nbsp; &nbsp;&nbsp; 3&nbsp; &nbsp; &nbsp;&nbsp; 8&nbsp; &nbsp; &nbsp;&nbsp; 0&nbsp; &nbsp; &nbsp; 125&nbsp; &nbsp; &nbsp;&nbsp; 8&nbsp; &nbsp;&nbsp; 4&nbsp; &nbsp; &nbsp; 16&nbsp; &nbsp; &nbsp;&nbsp; 1&nbsp; &nbsp; &nbsp;&nbsp; 62&nbsp; &nbsp; &nbsp; 16&nbsp; &nbsp;&nbsp; 5&nbsp; &nbsp; &nbsp; 16&nbsp; &nbsp; &nbsp;&nbsp; 1&nbsp; &nbsp; &nbsp;&nbsp; 31&nbsp; &nbsp; &nbsp; 32&nbsp; &nbsp;&nbsp; 6&nbsp; &nbsp; &nbsp; 16&nbsp; &nbsp; &nbsp;&nbsp; 0&nbsp; &nbsp; &nbsp;&nbsp; 16&nbsp; &nbsp; &nbsp; 64&nbsp; &nbsp;&nbsp; 7&nbsp; &nbsp; &nbsp; 80&nbsp; &nbsp; &nbsp;&nbsp; 0&nbsp; &nbsp; &nbsp; &nbsp; 8&nbsp; &nbsp;&nbsp; 128&nbsp; &nbsp;&nbsp; 8&nbsp; &nbsp;&nbsp; 208&nbsp; &nbsp; &nbsp;&nbsp; 0&nbsp; &nbsp; &nbsp; &nbsp; 4&nbsp; &nbsp;&nbsp; 256&nbsp; &nbsp;&nbsp; 9&nbsp; &nbsp;&nbsp; 464&nbsp; &nbsp; &nbsp;&nbsp; 0&nbsp; &nbsp; &nbsp; &nbsp; 2&nbsp; &nbsp;&nbsp; 512&nbsp; &nbsp; 10&nbsp; &nbsp;&nbsp; 976&nbsp; &nbsp; &nbsp;&nbsp; 0&nbsp; &nbsp; &nbsp; &nbsp; 1&nbsp; &nbsp; 1024Note that 976 == 1024 - 48 == 1024 - 32 - 16,that is:a(10) == 976 == sum { 0 .. 9 } of ( 2^i * (1 - P(i)) ) + 1But, how does P(i) relate to the initial number?</blockquote>

[QUOTE="tbitonti, post: 1349479, member: 10416"] [b]Every other prisoner ...[/b] Math geek alert. :p As an aside, the notes below are really a condensation of doing the solution by a complete simulation. Even the chart at the bottom is nearly so, as the numbers are a compression of the number ranges and offsets. Does anyone know a non-iterative way to solve this using elementary functions (or even using Fibonacci numbers, or a base 2 representation and a summation)? I put a mini-formula at the bottom, but it's just a start. Here are my notes (they read best with a fixed width font): from 1 .. 1000 [by 1] --> take out 1, 3, 5 .. 999 --> leaving 2 .. 1000 [by 2] [count == 1000] [count == 500] from 2 .. 1000 [by 2] --> take out 2, 6, 10 .. 998 --> leaving 4 .. 1000 [by 4] [count == 500] [count == 250] from 4 .. 1000 [by 4] --> take out 4, 12, 20 .. 996 --> leaving 8 .. 1000 [by 8] [count == 250] [count == 125] renumber by dividing by 8. from 1 .. 125 [by 1] --> take out 1, 3, 5 .. 125 --> leaving 2 .. 124 [by 2] [count == 125] [count == 62] from 2 .. 124 [by 2] --> take out 4, 8, 12 .. 124 --> leaving 2 .. 122 [by 4] [count == 62] [count == 31] from 2 .. 122 [by 4] --> take out 6, 14, 22 .. 118 --> leaving 2 .. 122 [by 8] [count == 31] [count == 16] from 2 .. 122 [by 8] --> take out 2, 18, 34 .. 114 --> leaving 10 .. 122 [by 16] [count == 16] [count == 8] from 10 .. 122 [by 16] --> take out 10, 42, 74 .. 104 --> leaving 26 .. 122 [by 32] [count == 8] [count == 4] from 26 .. 122 [by 32] --> take out 26, 90 --> leaving 58, 122 [by 64] [count == 4] [count == 2] from 58, 122 [by 64] --> take out 58 --> leaving 122 [by 128] [count == 2] [count == 1] Leaving 122. Backing up: 122 * 8 == 976. The 976'th prisoner is last. Model: Prisoner numbers: a(i) + (k - 1) * 2^i i gives the generation number a(i) is the number of the first prisoner k ranges from 1 .. K(i) K(i) is the number of prisoners remaining a(i) ... (K(i) - 1) * 2^i gives the prisoner number range The initial generation is generation 0, before any prisoners are removed. The initial prisoner number, a(0), is 1. The initial prisoner count, K(0), is 1000. Then: For each generation 'i' there is a parity of '0' or '1', where parity '0' means that the first prisoner will be removed, and parity '1' means that the second prisoner will be removed. P(i) == 0, 1 In the given problem, P(0) == 0. For a given 'i', 'P(i+1)' is given by: P(i+1) = P(i) if K(i) is even; P(i+1) = P(i) + 1 (mod 2) if K(i) is odd. For a given 'i', 'a(i+1)' is given by: a(i+1) = a(i) + 2^i if P(i) is 0; a(i+1) = a(i) if P(i) is 1. For a given 'i', 'K(i+1)' is given by: K(i+1) = K(i) / 2 if K(i) is even; K(i+1) = (K(i) + 1) / 2 if K(i) is odd and P(i) is 1; K(i+1) = (K(i) - 1) / 2 if K(i) is odd and P(i) is 0. Then: i a(i) P(i) K(i) 2^i 0 1 0 1000 1 1 2 0 500 2 2 4 0 250 4 3 8 0 125 8 4 16 1 62 16 5 16 1 31 32 6 16 0 16 64 7 80 0 8 128 8 208 0 4 256 9 464 0 2 512 10 976 0 1 1024 Note that 976 == 1024 - 48 == 1024 - 32 - 16, that is: a(10) == 976 == sum { 0 .. 9 } of ( 2^i * (1 - P(i)) ) + 1 But, how does P(i) relate to the initial number? [/QUOTE]

Verification