Abstract Math Help: "The game begins with n people on an island...."

[ccheney]

Hi. I've been having some problems with this question.

The game begins with n people on an island. The people are numbered 1 through n. Each day, the remaining islanders vote on whether the remaining islander with the highest number can stay on the island. If half or more of them say the person with the highest number must leave, then that person leaves the island and the game continues. Otherwise, the game ends and the remaining islanders split a million dollars equally. Assume the islanders act independently, are perfectly rational, and will vote in whatever way will give them the most money at the end. How low will the game last and how many people will remain on the island at the end?"

I've figured quite a bit of it out but I'm having trouble finishing the problem. Any help would be great, thanks.

 

[Deleted member 4993]

Hi. I've been having some problems with this question.

The game begins with n people on an island. The people are numbered 1 through n. Each day, the remaining islanders vote on whether the remaining islander with the highest number can stay on the island. If half or more of them say the person with the highest number must leave, then that person leaves the island and the game continues. Otherwise, the game ends and the remaining islanders split a million dollars equally. Assume the islanders act independently, are perfectly rational, and will vote in whatever way will give them the most money at the end. How low will the game last and how many people will remain on the island at the end?"

I've figured quite a bit of it out but I'm having trouble finishing the problem. Any help would be great, thanks.

Please share your work with us.

 

[ccheney]

Please share your work with us.

I've figured out the pattern, in that it resets to 1 at the Mersenne Primes. I know, based on the graph, it will involve some form a fractional part function.

The pattern is:
n = 1 2 3 4 5 6 7...15...31...
r(n) =1 2 1 2 3 4 1....1.....1...

Its easy to see the points that the pattern resets at are 2^n - 1, so the points in between must be (2^n -1)+y. Where 0<= y < (2^n -1). (sorry about the notation I'm not sure exactly how to express these symbols efficiently).

The part I'm struggling with is finding a concrete equation to express the pattern. Thank you for your help.

 

[JeffM]

I've figured out the pattern, in that it resets to 1 at 2^n -1. I know, based on the graph, it will involve some form a fractional part function.

The pattern is:
n = 1 2 3 4 5 6 7...15...31...
r(n) =1 2 1 2 3 4 1....1.....1...

Its easy to see the points that the pattern resets at are 2^n - 1, so the points in between must be (2^n -1)+y. Where 0<= y < (2^n -1). (sorry about the notation I'm not sure exactly how to express these symbols efficiently).

The part I'm struggling with is finding a concrete equation to express the pattern. Thank you for your help.

A formal proof may be time consuming, but the logic is simple.

Let's take an example. Suppose \(\displaystyle n = 15 = 2^4 - 1.\)

Those persons with numbers greater than 7 are 8, 9, 10, 11, 12, 13, 14, and 15.

That's 8 people, a majority, and they can stop the game. If they do so, they each get
1,000,000 / 15.

If they don't stop the game, there will be at most 7 with those numbers above 7 in later rounds and they cannot stop the game. Those with numbers below 8 will keep the game running to increase their share by eliminating anyone with a number greater than 7

1,000,000 / 15 < 1,000,000 / 14 < 1,000,000 / 13 and so on. So if 7 < n < 15, the game will keep running until there will be a final vote when those remaining are just 7.

That was obviously not a proof, but it shows what you are aiming to prove

\(\displaystyle \exists \ m \in \mathbb N^+ \text { such that } n = 2^m - 1 \implies\)

the game will last just one round and everyone will get \(\displaystyle \dfrac{1,000,000}{n}.\)

\(\displaystyle \exists \ m \in \mathbb N^+ \text { such that } 2^m \le n \le 2^{(m+1)} - 2 \implies\)

the game will last \(\displaystyle n + 2 - 2^m\) rounds and those with numbers

\(\displaystyle 1\) through \(\displaystyle 2^m - 1\) will each get \(\displaystyle \dfrac{1,000,000}{2^m - 1}.\)

 

[ccheney]

A formal proof may be time consuming, but the logic is simple.

Let's take an example. Suppose \(\displaystyle n = 15 = 2^4 - 1.\)

Those persons with numbers greater than 7 are 8, 9, 10, 11, 12, 13, 14, and 15.

That's 8 people, a majority, and they can stop the game. If they do so, they each get
1,000,000 / 15.

If they don't stop the game, there will be at most 7 with those numbers above 7 in later rounds and they cannot stop the game. Those with numbers below 8 will keep the game running to increase their share by eliminating anyone with a number greater than 7

1,000,000 / 15 < 1,000,000 / 14 < 1,000,000 / 13 and so on. So if 7 < n < 15, the game will keep running until there will be a final vote when those remaining are just 7.

That was obviously not a proof, but it shows what you are aiming to prove

\(\displaystyle \exists \ m \in \mathbb N^+ \text { such that } n = 2^m - 1 \implies\)

the game will last just one round and everyone will get \(\displaystyle \dfrac{1,000,000}{n}.\)

\(\displaystyle \exists \ m \in \mathbb N^+ \text { such that } 2^m \le n \le 2^{(m+1)} - 2 \implies\)

the game will last \(\displaystyle n + 2 - 2^m\) rounds and those with numbers

\(\displaystyle 1\) through \(\displaystyle 2^m - 1\) will each get \(\displaystyle \dfrac{1,000,000}{2^m - 1}.\)

Thank you so much for your help.

I'm still struggling to find an equation that represents rounds played as function of people. Using the graph, I've gotten to an equation that is similar to the the one I'm looking for, but I'm just can't figure out the transformation. Any help with this would be great, thank you!

 

[JeffM]

\(\displaystyle \text {number of people playing } = n \in \mathbb N^+.\)

\(\displaystyle \text {number of rounds played } = r(n).\)

Assuming I did not make a mistake in my previous post, the function relating r and n is defined "piecewise" and, to me, will look cumbersome expressed in strict function notation. Expressed as an algorithm it looks more comprehensible.

\(\displaystyle m = \lfloor log_2(n) \rfloor.\)

\(\displaystyle p = \lfloor log_2(n + 1) \rfloor.\)

\(\displaystyle q = p - m.\)

Notice that p, m, and q are are all functions of n and are all non-negative integers. Notice as well that q is either 0 or 1.

\(\displaystyle q = 1 \implies r(n) = 1.\)

\(\displaystyle q \ne 1 \implies r(n) = n + 2 - 2^m.\)