wu :: forums
wu :: forums - New Number System?

Welcome, Guest. Please Login or Register.
Dec 3rd, 2023, 1:10pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: Grimbal, Eigenray, towr, Icarus, ThudnBlunder, SMQ, william wu)
   New Number System?
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: New Number System?  (Read 1262 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
New Number System?  
« on: Jul 28th, 2014, 10:47pm »
Quote Quote Modify Modify

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).
IP Logged
dudiobugtron
Uberpuzzler
*****





   


Posts: 735
Re: New Number System?  
« Reply #1 on: Jul 29th, 2014, 12:53am »
Quote Quote Modify Modify

Yes, {0} Smiley
 
 
Edit: oh wait, you mean every non-negative integer, not just the ones in S...  Apologies.
« Last Edit: Jul 29th, 2014, 12:54am by dudiobugtron » IP Logged
dudiobugtron
Uberpuzzler
*****





   


Posts: 735
Re: New Number System?  
« Reply #2 on: Jul 29th, 2014, 1:29am »
Quote Quote Modify Modify

New answer: 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.

 
There is undoubtedly a more elegant way of proving it, though!
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: New Number System?  
« Reply #3 on: Jul 29th, 2014, 1:47am »
Quote Quote Modify Modify

on Jul 29th, 2014, 1:29am, dudiobugtron wrote:
We're now safe again up to 36 and 37 which need to be added.

 Huh
IP Logged
gotit
Uberpuzzler
*****





   
Email

Gender: male
Posts: 804
Re: New Number System?  
« Reply #4 on: Jul 29th, 2014, 6:59am »
Quote Quote Modify Modify

Once you add 16, you need not add 36 (4 + 16 * 2)
IP Logged

All signatures are false.
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2866
Re: New Number System?  
« Reply #5 on: Jul 29th, 2014, 7:42am »
Quote Quote Modify Modify

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

 
It's easier to see what's going on if you use binary:
 
hidden:
{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.

 
So the set S does exist .
IP Logged
dudiobugtron
Uberpuzzler
*****





   


Posts: 735
Re: New Number System?  
« Reply #6 on: Jul 29th, 2014, 4:01pm »
Quote Quote Modify Modify

on Jul 29th, 2014, 6:59am, gotit wrote:
Once you add 16, you need not add 36 (4 + 16 * 2)

Ah, thanks for spotting that!
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: New Number System?  
« Reply #7 on: Jul 29th, 2014, 10:47pm »
Quote Quote Modify Modify

Nice. Now, when the question was answered in affirmative, 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))?
 
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2866
Re: New Number System?  
« Reply #8 on: Jul 30th, 2014, 6:32am »
Quote Quote Modify Modify

From my earlier answer, if the numbers are: 1, b>1 then S(1, b) exists and is all numbers of form Sumi{aib2i} with ai in [0,b) for all i
 
For S to exist, then 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
 
So, depending on which flavour of natural numbers we're using (including or excluding 0) there are only 1 or 2 cases left:
 
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)
 
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).
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: New Number System?  
« Reply #9 on: Jul 31st, 2014, 8:39am »
Quote Quote Modify Modify

Nothing to add, rmsgrey.
 
Excellent analysis.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board