wu :: forums « wu :: forums - New Number System? » Welcome, Guest. Please Login or Register. Dec 3rd, 2023, 1:10pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: Grimbal, Eigenray, towr, Icarus, ThudnBlunder, SMQ, william wu)    New Number System? « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: New Number System?  (Read 1262 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: 2866
 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: 2866
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

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