- #1
roadrunner
- 101
- 0
I have 2 questions here. I know there is a lot of text, but don;t be scared or deterred from helping please, it is simple to understand and mostly just text/explanation. The Second one is very long, the first not so much.
1)Problem: Complete the proof of Observation 4.2 by showing that every positive integer has exactly one binary expansion. Obs 4.2 just shows that every integer has at least one binary expansion. I need to show that it has exactly one
Proposed Solution
Every binary number can be represented by 1’s and 0’s. For example: 27=2^4+ 2^3+2^1+1. If we look at this we see that what we really have is 27=1*2^4+ 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0.
Removing the 2^i s we are left with 1’s and 0’s. In this example they would be 11011, which is the binary number of 27.
More generally, n=sum(from j=0 to k) of aj2^j with each aj=1 or 0 and ak=1.
1 would be 1=1*2^0
2 would be 10 =1*2^1
3 would be 11 =1*2^0+1*2^1
4 would be 100 = 1*2^2+0*2^1+0*2^0
10 would be 1010=1*2^3+0*2^2+1*2^1+0*2^0
etc.
To prove that each binary expansion is unique we look at these binary forms (1010 etc). To return to decimal form we expand them as above (2^3+0*2^2+1*2^1+0*2^0 etc). Since going from binary to decimal gives a unique number and since we know every number can be represented in binary, we must assume that every binary expansion is unique.
By contradiction, if the binary expansion was not unique, then we would be able to expand a binary number such as 1010 into 2^3+0*2^2+1*2^1+0*2^0, and come up with a solution other than 10. Since this is not possible, the binary expansions of integers must be unique.
2) Problem : There are five perfectly logical pirates numbered 1,2,3,4,5 who have a booty
of 100 gold pieces to divide among them. They have decided upon the following scheme for
splitting up the gold: First pirate 1 suggests a division (i.e. which pirate gets how much),
then each pirate votes on this scheme. If it receives a majority of votes, this scheme is
used to split the gold. Otherwise, pirate 1 is thrown overboard, and it is pirate 2's turn to
suggest a division among the remaining four pirates. The remaining four pirates then vote
on pirate 2's scheme. If it receives a strict majority (more than half) of votes, then it is
adopted. Otherwise pirate 2 is thrown overboard, and it is then pirate 3's turn to suggest
a division scheme among the remaining pirates. Similarly, pirate 4 and then pirate 5 will
suggest division schemes if the earlier ones are thrown overboard. Assume that each pirate
has the following priorities: first they wish to maximize the amount of gold they receive,
and subject to this, they wish to throw as many people overboard as possible. (Note that
each pirate is not worried about themselves getting thrown overboard). How will the gold
be divided?
Proposed Solution
For this problem I made several assumptions. First off, since every pirate is perfectly logical, then it should be assumed that if there are two pirates left and pirate 2 has to choose between a 100:0 and 99:1 ratio, he should take the 99:1 ratio since it is better to get 1 piece of gold than none. Secondly, since the problem states that a majority means more than half, then if there are 4 pirates left and 2 vote yes and two vote no, then the 2nd pirate is thrown over board (as two yes’ are equal to half and not greater than half. The same applies for one yes and one no with two pirates). I also assumed that each pirate voted yes for his own strategy (why would he vote no?). Lastly, I assumed that each pirate knew that the other pirates were logical and would maximize their own money.
If we look backwards we can solve this problem.
If there are two pirates left, then pirate 5 (P5) can say no to any offer that P4 makes and take 100 coins. P5’s optimal strategy is to have 2 pirates left.
If there are three pirates left, then P3 should suggest a 99:1 ratio split between P3 and P4. In this case P5 should say no to any offer, since he knows that he could get 100 coins if the vote fails. However, since he is logical (and therefore smart) he should know that P3 will vote yes and if any money is given to P4, then P4 will vote yes. Therefore P5’s opinion does not matter. Therefore, P3 and P5 would say yes and the money would be split with 99 to P3 and 1 to P4 and 0 to P5.
If there are four pirates left, P2 needs to make an offer than two other pirates like or he will be thrown overboard and get 0 coins. P5 wants to say yes to any offer that gets himself more than 0 coins and P4 wants to say yes if he gets more than 1 coin (If P4 was offered one coin, some may think that this is the same situation as when there are three pirates where P4 gets one coin, however it is not. If P4 is offered one coin with four pirates remaining he should say no since there is a chance that P3 will give him 2 coins when there are 3 pirates remaining). P3 will say no as he knows if the vote fails he can get 99 coins. Therefore, P2 should give himself 97 coins, P4 2 coins, P5 1 coin and P3 0 coins.
If there are five pirates left, P1 needs to make an offer that 2 other pirates like. For similar reasoning as when four pirates remain, P1 should give himself 95 coins, P2 and P3 0 coins, P4 3 coins and P5 2 coins.
Thus the coins will be divided 95, 0, 0, 3, 2, for P1 through P5 respectively.
Alternate: However, the problem also states that each pirate wants to throw as many other pirates over as possible. If that is true then P5 ends up with 100 coins and everyone else none. But personally, I do not think that makes the 5 pirates very logical as there is a way that they can get more coins.
NOTE: Although the question states that each pirate is not concerned with being thrown over, this seems odd. If a pirate is thrown over he gets 0 coins and since he is logical he should want to avoid being thrown over.
1)Problem: Complete the proof of Observation 4.2 by showing that every positive integer has exactly one binary expansion. Obs 4.2 just shows that every integer has at least one binary expansion. I need to show that it has exactly one
Proposed Solution
Every binary number can be represented by 1’s and 0’s. For example: 27=2^4+ 2^3+2^1+1. If we look at this we see that what we really have is 27=1*2^4+ 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0.
Removing the 2^i s we are left with 1’s and 0’s. In this example they would be 11011, which is the binary number of 27.
More generally, n=sum(from j=0 to k) of aj2^j with each aj=1 or 0 and ak=1.
1 would be 1=1*2^0
2 would be 10 =1*2^1
3 would be 11 =1*2^0+1*2^1
4 would be 100 = 1*2^2+0*2^1+0*2^0
10 would be 1010=1*2^3+0*2^2+1*2^1+0*2^0
etc.
To prove that each binary expansion is unique we look at these binary forms (1010 etc). To return to decimal form we expand them as above (2^3+0*2^2+1*2^1+0*2^0 etc). Since going from binary to decimal gives a unique number and since we know every number can be represented in binary, we must assume that every binary expansion is unique.
By contradiction, if the binary expansion was not unique, then we would be able to expand a binary number such as 1010 into 2^3+0*2^2+1*2^1+0*2^0, and come up with a solution other than 10. Since this is not possible, the binary expansions of integers must be unique.
2) Problem : There are five perfectly logical pirates numbered 1,2,3,4,5 who have a booty
of 100 gold pieces to divide among them. They have decided upon the following scheme for
splitting up the gold: First pirate 1 suggests a division (i.e. which pirate gets how much),
then each pirate votes on this scheme. If it receives a majority of votes, this scheme is
used to split the gold. Otherwise, pirate 1 is thrown overboard, and it is pirate 2's turn to
suggest a division among the remaining four pirates. The remaining four pirates then vote
on pirate 2's scheme. If it receives a strict majority (more than half) of votes, then it is
adopted. Otherwise pirate 2 is thrown overboard, and it is then pirate 3's turn to suggest
a division scheme among the remaining pirates. Similarly, pirate 4 and then pirate 5 will
suggest division schemes if the earlier ones are thrown overboard. Assume that each pirate
has the following priorities: first they wish to maximize the amount of gold they receive,
and subject to this, they wish to throw as many people overboard as possible. (Note that
each pirate is not worried about themselves getting thrown overboard). How will the gold
be divided?
Proposed Solution
For this problem I made several assumptions. First off, since every pirate is perfectly logical, then it should be assumed that if there are two pirates left and pirate 2 has to choose between a 100:0 and 99:1 ratio, he should take the 99:1 ratio since it is better to get 1 piece of gold than none. Secondly, since the problem states that a majority means more than half, then if there are 4 pirates left and 2 vote yes and two vote no, then the 2nd pirate is thrown over board (as two yes’ are equal to half and not greater than half. The same applies for one yes and one no with two pirates). I also assumed that each pirate voted yes for his own strategy (why would he vote no?). Lastly, I assumed that each pirate knew that the other pirates were logical and would maximize their own money.
If we look backwards we can solve this problem.
If there are two pirates left, then pirate 5 (P5) can say no to any offer that P4 makes and take 100 coins. P5’s optimal strategy is to have 2 pirates left.
If there are three pirates left, then P3 should suggest a 99:1 ratio split between P3 and P4. In this case P5 should say no to any offer, since he knows that he could get 100 coins if the vote fails. However, since he is logical (and therefore smart) he should know that P3 will vote yes and if any money is given to P4, then P4 will vote yes. Therefore P5’s opinion does not matter. Therefore, P3 and P5 would say yes and the money would be split with 99 to P3 and 1 to P4 and 0 to P5.
If there are four pirates left, P2 needs to make an offer than two other pirates like or he will be thrown overboard and get 0 coins. P5 wants to say yes to any offer that gets himself more than 0 coins and P4 wants to say yes if he gets more than 1 coin (If P4 was offered one coin, some may think that this is the same situation as when there are three pirates where P4 gets one coin, however it is not. If P4 is offered one coin with four pirates remaining he should say no since there is a chance that P3 will give him 2 coins when there are 3 pirates remaining). P3 will say no as he knows if the vote fails he can get 99 coins. Therefore, P2 should give himself 97 coins, P4 2 coins, P5 1 coin and P3 0 coins.
If there are five pirates left, P1 needs to make an offer that 2 other pirates like. For similar reasoning as when four pirates remain, P1 should give himself 95 coins, P2 and P3 0 coins, P4 3 coins and P5 2 coins.
Thus the coins will be divided 95, 0, 0, 3, 2, for P1 through P5 respectively.
Alternate: However, the problem also states that each pirate wants to throw as many other pirates over as possible. If that is true then P5 ends up with 100 coins and everyone else none. But personally, I do not think that makes the 5 pirates very logical as there is a way that they can get more coins.
NOTE: Although the question states that each pirate is not concerned with being thrown over, this seems odd. If a pirate is thrown over he gets 0 coins and since he is logical he should want to avoid being thrown over.