What is the Unique Function Possessing Certain Properties on Positive Integers?

[K Sengupta]

Consider all functions g from the positive integers to the positive integers such that:
(a) For each positive integer p there exists an unique positive integer q such that g(q) = p;
(b) For each positive integer q, we have g(q+1) as either 4g(q) -1; or;
g(q) -1.
Determine the set of positive integers s such that:
g(1999) = s; for some function g possessing both the properties (a) and (b).

 

[Moo Of Doom]

I get {1072, 2096}[/color] as the set of solutions.

 

[AKG]

If g(1) = 3, since g is 1-1 and onto, g(2) must be 2, g(3) must be 1. Why must g(2) be 2? Well since g is onto, it must at some point be 2, and if g(2) is not 2, then it is 4(3)-1 = 11. The only way g can be 2 at some later point is if it eventually decreases, but it can only decrease one number at a time, so if it is to decrease from 11 to 2, and it can only decrease one number at a time, then it will eventually pass through 3 again, contradicting the fact that g must be 1-1. In fact, if g(1) > 3, we get this contradiction.

If g(1) = 1, then obviously g(2) = 4-1 = 3 (otherwise g(2) = 1-1 = 0, which isn't a positive integer). By a similar argument to the one above, g must eventually pass through 2, and so it must go from 3 to 2, because once it increases past 3, it can never come down to 2 without passing through 3 again. So g(3) = 2. Since g can't decrease again, otherwise it would return to 1, making it non-injective, g(4) = 7. Applying the same argument again and again, we see (g(1), g(2), g(3), ...) must be the sequence:

1, 3,2, 7,6,5,4, 15,14,...,9,8, 31,30,...,17,16 63,62,...,33,32, and so on

Assuming g starts at 1. The other alternative is g starts at 2. We will get:

2,1, 3, 11,10,...,5,4, 15,14,13,12, 47,46,...,17,16, 63,62,...,49,48, and so on

Doing some arithmetic, it will be easy but tedious to find what the 1999^th term is in each of these sequences, giving the two possibilities for s.

 

[Moo Of Doom]

Actually, I don't think g(1) can be 3. Since 1 must be in the range of g, we have g(k)=1 for some k. But then g(k+1)=1-1=0 or g(k+1)=4(1)-1=3. Since we know the first case can't be true (since 0 is not in the co domain of g), We must have g(k+1)=3. But g is injective, so g(1)=3=g(k+1) implies 1=k+1. But this means k=0, which is not in the domain of our function. This contradicts the fact that 1 is in the range of g, and thus we can't have g(1)=3.

g(1)=1 and g(1)=2 are the only possibilities.

The one with g(1)=1 is easy. I solved that with some clever arithmetic and pattern finding. g(1)=2 proved far more challenging, and I resorted to Mathematica to produce the answer for that case. :(

 

[AKG]

But g is injective, so g(1)=3=g(k+1) implies 1=k+1. But this means k=0, which is not in the domain of our function. This contradicts the fact that 1 is in the range of g, and thus we can't have g(1)=3.

Yeah, but g(1) can't be 3.

 

[Moo Of Doom]

Yeah, but g(1) can't be 3.

Precisely what I was proving in that post.

 

[AKG]

Precisely what I was proving in that post.

Why were you proving that?

 

[Moo Of Doom]

The same reason you proved it in your post...

It leads to the simple conclusion that if g(1) > 2, we can't have a bijective function satisfying (b). g(q-1)-1 is a decreasing sequence, 4g(q-1)-1 is an increasing sequence. If g(1)>=3 then either 3 is not in the range of g, or 3 is hit before 1. But 3 must come after 1, so we're done. Aiyah! Another proof.

Anyway, the answers are in {1072, 2096}. I'd love to see someone figure out the second one without doing all the arithmetic though...

 

[Playdo]

Consider all functions g from the positive integers to the positive integers such that:
(a) For each positive integer p there exists an unique positive integer q such that g(q) = p;
(b) For each positive integer q, we have g(q+1) as either 4g(q) -1; or;
g(q) -1.
Determine the set of positive integers s such that:
g(1999) = s; for some function g possessing both the properties (a) and (b).

So (a) tells me the map is one to one and onto on the natural numbers, it is an isomorphism. (b) actually defines the function itself as

g(q) = p (p here is not to be construed as prime)

g(q+1) = 4g(q)-1 = 4p-1 OR g(q+1) = g(q) - 1 = p - 1

Well by the rules of the game we must have

g(1) = 3 since 1-1 = 0 is not a natural number (positive integer)
g(2) = 2 since no other number can be mapped to two save three under the rules
g(3) = 1 since no other number can be mapped to one save two under the rules
g(4) = 15 since 1-1 = 0 is not a natural number.
g(5) = 14
g(6) = 13
g(7) = 12
g(8) = 11
g(9) = 10
g(10) = 9
g(11) = 8
g(12) = 7
g(13) = 6
g(14) = 5
g(15) = 4?
g(16) = 15? already mapped so we have to step back and do
g(15) = 19
g(16) = 18
g(17) = 17
g(18) = 16
g(19) = 63
.
.
.
.
etc. So such a function does exist. But the questions that remain are several, is g a unique map or are there many ways to do it? If there is only one function g that satisfies the properties then there is only one s satisfying the question. What we should do is try understand the class of acceptable functions {g}. Notice in the above construction everything up to g(4) is unique but g(5) can be either 14 or 63? If one of these two choices proves impossible we might have a clue.

Think of this function as being peicewise and in some sense it is like an automoton. If we choose g(q+1) = g(q)-1 we can move backwards in stepwise fashion. If we choose g(q+1) = 4g(q)-1 we are jumping ahead roughly by a factor of four. It stands to reason that any function g that satisfies the requirements must have the property that for any jump g(q+1)=4g(q)-1, there must exist t such that g(q+1+t) = 4g(q)-1-t = g(s) for some s less than q+1. We would then only be able to backtrack to t-1 since the next jump forward would have to come at g(s+2)=4(4g(q)-t)-1
The trick is to know when the jump is too large to be covered by the available leftover numbers.

So consider this

g(1) = 3
g(2) = 7
g(3) =11
g(4) =15

Notice that 3 insulates 1 and 2 from the higer order four mod threes terms, I have to fill in the gaps by sequentially moving doen from one of the 4p-1. Therefore if I do not account for every integer less than three in the steps before I allow a 4p-1 the condition of 1 to 1 and onto is broken.

So we have to have

g(1) = 3
g(2) = 2
g(3) = 1
g(4) = 15

Now if I allow g(q+1) = 4g(q)-1 before I have accounted for the integers 4,5,6,...14 g is not a valid map under the conditions. So it must be that g(15) = 4 but that implies g(16) = 15 which has already been mapped violating the conditions. So if we go to g(14) = 5 and then g(15) = 19, we have now excluded permanently the number 4. No such function g can exist under these circumstances. Furthermore we would also have to use g(q+1) = g(q)-1 to backtrack and cover everything down to sixteen. Let's pick that up.

g(1) = 3
g(2) = 2
g(3) = 1
g(4) = 15
g(5) = 14
g(6) = 13
g(7) = 12
g(8) = 11
g(9) = 10
g(10) = 9
g(11) = 8
g(12) = 7
g(13) = 6
g(14) = 5 (note 4 is not accounted for)
g(15) = 19
g(16) = 18
g(17) = 17
g(18) = 16
g(19) = 63 (use g(q+1) = g(q)-1 24 times)
.
.
.
g(43) = 20
g(44) = 79 (use g(q+1) = g(q) - 1 16 times)
g(60) = 64

If we adjust the caveats so that we say there is a one to one and onto mapping of N to N-{4} having the properties we are working again. Then there is a pattern starting to develop that is the numbers q that correspond to g(q+1)=4g(q)-1 can be listed once we have passed 4.

so we have

g(15) = 4(5)-1 = 19
g(19) = 4(16)-1 = 63
g(63) = 4(20)-1 = 79
g(79) = 4(64)-1 = 255
g(255) = 4(80)-1 = 319
g(319) = 4(256)-1 = 1015
g(1015) = 4(320) - 1 = 1279
g(1279) = 4(1016) - 1 = 4063

Now we can stop and start counting backwards, so that we have

g(1279+t) = 4063 - t = s

So when 1279+t = 1999 we find that t = 1999-1279=720 and 4063 - 720 = 3343 = s. Thus with the above caveats noted the only possible value for s is 3343.

I like this problem because it sort of turns counting on it's head. We like to count sequentially but here we have to count differently depending on which side of the map we are looking at. Very nice problem!

Also if we allow ourselves the inclusion of zero among the positive integers then

g(0) = 4 (and thus four is acounted for)
g(1) = 3
g(2) = 2
.
.
.

The answer is not changed but the apparent exclusion of four is explained.

 

[shmoe]

Anyway, the answers are in {1072, 2096}. I'd love to see someone figure out the second one without doing all the arithmetic though...

It's not that hard to do by hand, you'll get the sequence

2, 1, 3, 11, 10, ..., 4, 15, 14, ..., 12, 47, 46, ..., 16, 63, 62, ...48, ...

just group as:

(2, 1), (3), (11, 10, ..., 4), (15, 14, ..., 12), (47, 46, ..., 16), (63, 62, ...48), ...

the number of elements in the groups are:

2, 1, 8, 4, 32, 16, 128, 64, ...

You can sort out what happens in a group without knowing what happened in the earlier ones. For example, the 128 group will contain the numbers greater than 2+1+8+4+32+16=63 and less than or equal to 2+1+8+4+32+16+128=191 in reverse order (general pattern is similar). So if we want g(q)=187, the corresponding q is 68. Not much more work to get g(q)=1999.

 

[shmoe]

Well by the rules of the game we must have

g(1) = 3 since 1-1 = 0 is not a natural number (positive integer)
g(2) = 2 since no other number can be mapped to two save three under the rules
g(3) = 1 since no other number can be mapped to one save two under the rules
g(4) = 15 since 1-1 = 0 is not a natural number.

rule b tells you g(4) is either g(3)-1=0 or 4*g(3)-1=3, nether work of course, but 15 isn't an option.

 

[Playdo]

rule b tells you g(4) is either g(3)-1=0 or 4*g(3)-1=3, nether work of course, but 15 isn't an option.

Oops! Yeah you are right.

g(1) = 1
g(2) = 3
g(3) = 2
g(4) = 7 Now I see a clear pattern g(2^n)=2^(n+1)-1 So find 2^n
g(5) = 6 that is just the largest smaller than 1999 and work backwards.
g(6) = 5 It should be 1024 = 2^10, g(2^10) = 2^11-1 = 2047
g(7) = 4 count forward to 1999 using the g(q) = q-1 option
g(8) = 15 g(1024+975) = 2047-975 = 1079
g(9) = 14 The million dollar question is this g unique? I will venture to
g(10) = 13 say yes it is. But I will leave the proof to someone else.
g(11) = 12
g(12) = 11
g(13) = 10
g(14) = 9
g(15) = 8
.
.
.