Solving Observation 4.2: Showing Every Integer Has Exactly One Binary Expansion

In summary: Therefore, if P2 offers 10 coins to P5 and P5 votes yes, then P2 gets 11 coins. If there are five pirates left, then P1 should say no to any offer that two other pirates like and throw one of the other three pirates overboard. P1’s optimal strategy is to have four pirates left. In summary, the gold will be divided as follows: Pirate 1 will get 10 coins, Pirate 2 will get 11 coins, Pirate 3 will get 10 coins, and Pirate 4 and Pirate 5 will get 0 coins.
  • #1
roadrunner
103
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.
 
Physics news on Phys.org
  • #2
The most common way to do the representation problem is to count the number of representations for a number x to the base b (in this case b=2) and obviously the result will be 1.

To see this, if (a1, ..., an) is a representation for x, then (a1, ..., an) - 1 is a representation for x-1. After a little algebra we can conclude that for any representation of x, call it r, we can use r to find a representation of x-1.

I'm not sure how formal you want the proof or if it's homework.
 
Last edited:
  • #3
its homework :)
 
  • #4
Then consider that my homework hint :)

I'm not convinced by your argument at all. You say: "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." Why is it not possible? That's what you should be proving.
 
  • #5
Proving that the representations of integers are unique is pretty important, especially because the binary representations of, say, rational numbers are NOT unique.
 

Related to Solving Observation 4.2: Showing Every Integer Has Exactly One Binary Expansion

1. What is the significance of showing every integer has exactly one binary expansion?

The significance of this observation is that it proves the uniqueness of binary representation for integers. It means that every integer can be represented uniquely in binary form, which is essential for various computer algorithms and operations.

2. How is this observation relevant in the field of computer science?

This observation is highly relevant in computer science as binary representation is the foundation of digital computing. It is used in various operations, such as data storage, arithmetic calculations, and logical operations. The uniqueness of binary expansion for integers ensures the accuracy and consistency of these operations.

3. What is the proof behind this observation?

The proof behind this observation is based on the concept of positional notation. In binary representation, each digit's value depends on its position relative to the decimal point. This ensures that each integer has a unique binary expansion, as changing the positions of the digits would result in a different value.

4. Can you provide an example to illustrate this observation?

Sure, for example, the integer 5 can be represented in binary as 101. If we change the positions of the digits, say 110, the value would become 6. This shows that changing the positions of digits results in a different integer, proving the uniqueness of binary expansion for each integer.

5. How does this observation relate to other number systems?

This observation is specific to the binary number system, but it can also be applied to other number systems. For example, in the decimal system, each integer has a unique decimal expansion, and changing the positions of digits would result in a different value. However, this uniqueness is not true for all number systems, such as the Roman numeral system.

Similar threads

  • Math Proof Training and Practice
2
Replies
40
Views
14K
  • Special and General Relativity
Replies
2
Views
1K
Replies
16
Views
7K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
Replies
2
Views
1K
  • Special and General Relativity
2
Replies
53
Views
9K
  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
4K
Back
Top