wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> New Number System?
        
(Message started by: Barukh on Jul 28^th, 2014, 10:47pm)

Title: New Number System?
Post by Barukh on Jul 28^th, 2014, 10:47pm

Does there exist a set S of non-negative integers, such that every non-negative integer is represented as s + 2t in a unique way (s, t are of course elements of S).

Title: Re: New Number System?
Post by dudiobugtron on Jul 29^th, 2014, 12:53am

Yes, {0} :)

Edit: oh wait, you mean every non-negative integer, not just the ones in S... Apologies.

Title: Re: New Number System?
Post by dudiobugtron on Jul 29^th, 2014, 1:29am

New answer: [hide]No. Outline of proof by construction:

We can construct the set by finding (in size order) each integer we can't currently represent from members of S, and adding them to S. So, the set must containt 0 (0+2*0) and 1 (1+2*0), after which we can represent 2 (0+2*1) and 3 (1+2*1). We then need to add 4 and 5, which are otherwise unrepresentable, so the set is {0,1,4,5,...}. With these we can represent all the numbers up to 15 (5+2*5), and so need to add 16 and 17 to the set. Because we had such a big gap, we also need to add 20, and 21. We're now safe again up to 36 and 37 which need to be added.

So the set is now {0,1,4,5,16,17,20,21,36,37,...}. But this is where we get our contradiction; as 44 can be represented as 36+2*4, or 4+2*20.

Thus, unless I have made an error in my construction (you're welcome to construct it for yourself to check), no such set S exists.[/hide]

There is undoubtedly a more elegant way of proving it, though!

Title: Re: New Number System?
Post by Barukh on Jul 29^th, 2014, 1:47am

on 07/29/14 at 01:29:26, dudiobugtron wrote:

[hide]We're now safe again up to 36 and 37 which need to be added.[/hide]

???

Title: Re: New Number System?
Post by gotit on Jul 29^th, 2014, 6:59am

[hide]Once you add 16, you need not add 36 (4 + 16 * 2)[/hide]

Title: Re: New Number System?
Post by rmsgrey on Jul 29^th, 2014, 7:42am

[hideb]{0, 1, 4, 5, 16, 17, 20, 21} gives you [0,63].[/hideb]

It's easier to see what's going on if you [hide]use binary[/hide]:

[hideb]{0, 1, 100, 101, 10000, 10001, 10100, 10101, ...} - it's immediately obvious that S is all the numbers with unset even bits - and any number can be broken down uniquely into its odd bits and its even bits - the odd bits giving a number in S, and the even bits twice a number in S.[/hideb]

So the set S [hide] does exist [/hide].

Title: Re: New Number System?
Post by dudiobugtron on Jul 29^th, 2014, 4:01pm

on 07/29/14 at 06:59:35, gotit wrote:

[hide]Once you add 16, you need not add 36 (4 + 16 * 2)[/hide]

Ah, thanks for spotting that!

Title: Re: New Number System?
Post by Barukh on Jul 29^th, 2014, 10:47pm

Nice. Now, when the question was answered in [hide]affirmative[/hide], let's ask a more general question:

For which natural numbers n, m, there exists a set S(n, m) of non-negative integers, such that every non-negative integer is represented as ns + mt in a unique way (s, t are elements of S(n, m))?

Title: Re: New Number System?
Post by rmsgrey on Jul 30^th, 2014, 6:32am

From my earlier answer, if the numbers are: [hide]1, b>1[/hide] then [hide]S(1, b) exists and is all numbers of form Sum_i{a_ib²ⁱ} with a_i in [0,b) for all i[/hide]

For S to exist, then [hide]it must be possible to make 1, which can only be 1+0, which can only be 1*1 + m*0 (or 1*1 + 0*t or some equivalent with n, m swapped) so for s to exist, at least one of n, m must be 1[/hide]

So, depending on which flavour of natural numbers we're using (including or excluding 0) there are only 1 or 2 cases left:

[hide]S(1,1) does not exist - if you try constructing S, to make 0 you need to include 0, and to make 1, you need to include 1, but then both s=0, t=1 and s=1, t=0 give 1. If you don't regard that as different, then you can't make 3 without including 2 or 3 in S; including 2 gives you multiple ways to make 2, while including 3 means you then can't make 5 without 4 (giving multiple ways to make 4) or 5 (giving multiple ways to make 6)[/hide]

[hide]S(0,1) does not exist - S needs to have an infinite number of members to make enough combinations for the infinite number of numbers, but that means that there's an infinite number of ways of making 0 (0*s+1*0 for any s).[/hide]

Title: Re: New Number System?
Post by Barukh on Jul 31^st, 2014, 8:39am

Nothing to add, rmsgrey.

Excellent analysis.