Author |
Topic: New Number System? (Read 1307 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
New Number System?
« on: Jul 28th, 2014, 10:47pm » |
 Quote  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 Modify
|
Yes, {0} 
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 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:
Posts: 2276
|
|
Re: New Number System?
« Reply #3 on: Jul 29th, 2014, 1:47am » |
Quote Modify
|
on Jul 29th, 2014, 1:29am, dudiobugtron wrote:| We're now safe again up to 36 and 37 which need to be added. |
|
|
|
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: New Number System?
« Reply #4 on: Jul 29th, 2014, 6:59am » |
Quote Modify
|
Once you add 16, you need not add 36 (4 + 16 * 2)
|
|
IP Logged |
All signatures are false.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: New Number System?
« Reply #5 on: Jul 29th, 2014, 7:42am » |
Quote 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 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:
Posts: 2276
|
|
Re: New Number System?
« Reply #7 on: Jul 29th, 2014, 10:47pm » |
Quote 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
Gender:
Posts: 2873
|
|
Re: New Number System?
« Reply #8 on: Jul 30th, 2014, 6:32am » |
Quote 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:
Posts: 2276
|
|
Re: New Number System?
« Reply #9 on: Jul 31st, 2014, 8:39am » |
Quote Modify
|
Nothing to add, rmsgrey.
Excellent analysis.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print