Archived

This topic is now archived and is closed to further replies.

ToohrVyk

A weird function.

Recommended Posts

ToohrVyk    1595
I want to define a function f : [0,1] -> [0,1] so that, for any 0 <= a < b <= 1 and 0 <= y <= 1, there is c in ]a, b[ for which f(c) == y. How would you go about doing this? I''ve heard there are quite a few solutions. Below is my solution. ---------------------------- ***Definition Firstly, f(1) = 1; Let x be a number in [0,1[. I will write x = 0,x1x2x3x4x5... in base 11. If there is an infinity of A digits, then f(x) = 1. If there is a finite number of A digits, I define recursively two series: u(0) = 0, u(n+1) = if (xn == A) then 0 else u(n)+1; v(0) = 0, v(n+1) = if (xn == A) then 0 else v(n) + xn/10^(u(n)) Since there is a finite number of A digits, there is a biggest N for which xN == A, and if N'' > N, xN'' != A. This means that starting with N, u(n) is growing at a rate of 1. Also, v(n) is a growing series that is always below 1, which means it has a limit. We define f(x) = lim v ***Now it''s defined, let''s check it has the right properties. Take a, b, y. Let a = 0,a1a2a3a4... in base 11. Let L = log(11)(b-a). Let N > L so that aN != A. let x = 0,a1a2....a(N-1)Ax1x2x3x4... if y == 1 then x1=x2=x3=...=A so f(X) = 1 = y if y == 0,y1y2y3y4y5y6... in base 10, then for each n, xn = yn, so f(X) = 0,y1y2y3.... = y

Share this post


Link to post
Share on other sites
Zipster    2359
Even if this was homework, I for one think that the OP has put an honorable amount of work and time into solving this themselves, and I can only feel compelled to help out

However I''ve never seen the notation x = 0,x1x2x3x4x5... before, and the part about it being in base 11 doesn''t really give me much clue Are you referring to the actual digits of the number? Lastly, it''s been a while since I''ve seen something like ]a, b[ used. Is this another way of saying [0,a] U [b,1]? Sorry for confusion over notation, I''ve just never seen it before!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
quote:
Original post by Zipster
Lastly, it''s been a while since I''ve seen something like ]a, b[ used. Is this another way of saying [0,a] U [b,1]? Sorry for confusion over notation, I''ve just never seen it before!

I guess in the US you usually write (a,b). It denotes an open interval.

Share this post


Link to post
Share on other sites
Keem    138
quote:
Original post by ToohrVyk
A question from a test last year. Here, in France, July-August is holidays, so no homework.


You don't get bugger loads of homework to do over the holidays?!? Blimey, what do you do with yourself without any maths to do for two months?

edit: Anyway, i rekon your solution looks good, i havn't scrutinised the proof too much mind you. I can;t help thinking that this question is beggin for a reference to some of the standard analysis theorems that you were no doubt taugght in your course. I never did much real analysis at uni ( i stuck to the complex kind, much neater and easier ) so I could tell you any more.

[edited by - Keem on August 15, 2003 5:57:45 AM]

Share this post


Link to post
Share on other sites
Zipster    2359
Ah, I see. Yes, we do use the parenthesis in the US more often to denote open intervals, although now that I think about it I do vaguely remember one of my books using the "backwards bracket" notation once, maybe twice... at any rate, I hope you are correct because I'll be assuming that for the rest of this post!

As far as I can tell, you're looking for a continuous function that maps an open-interval domain to a closed-interval range. The function can't be f : [0,1] -> [0,1], at least by the criteria you have provided. The only functions I can think of off the top of my head that have this property are sine and cosine, but even then the domain is (-inf, +inf), which I feel might be "cheating" a bit because they're periodic, but oh well You might be able to map 'c' in the range (a, b) to a 'd' in the range (0, PI/4), then plug that into sin. However it's still going to be tough to get the closed domain, because only at 0 and PI/4 does sin output 0 and 1 respectively.

I might be really far off though, so excuse any ignorance on my part

[edited by - Zipster on August 15, 2003 6:20:06 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
As far as I can tell, he''s looking for a function that maps ANY open interval in the domain to the whole range [0,1]. I don''t know how to contruct such a function, but it can''t be continuous, as far as I understand.

Share this post


Link to post
Share on other sites
ToohrVyk    1595
AP: Yes, it can't be continuous. Proof:

let a in [0,1], e > 0. There is an x in (a-e,a+e) so f(x) = 1, an y in (a-e,e=a+e) so f(y) = 0. So when e tends towards 0, we have a series x(n)->a so that f(x(n)) = 1, and a series y(n)->a so that f(y(n)) = 0. This means lim(a) f is undefined, so f isn't continuous in a.

Keem: actually I don't get any real homework at all for two years. I'm preparing a "competition" to enter one of the greater schools in my country, so I'm meant to work all by myself: get my own books, choose my "homework" and do it. Sure, teachers teach us, and guide us into what we might want working more. Besides, we have a thing called "kholle", where three students and a teacher reunite for an hour in a classroom. Each student is given as many exercises as he can take during that hour, and he must solve each before going on to the next one.

EDIT to Keem: also, I've been give the teacher's solution to this problem. It's almost like the one above (it defines f(x) as the limit of A(n)/n, where A(n) is the number of "1" in the n first digits after the point ). It's just that I feel there might be some other, algebra-based, solution.

Zipster: yes, ]a,b[ = { x in IR | a < x < b }, and if I write x = 0,x1x2... I mean xn is the nth digit of x. Also, like I said this question was one of 32 questions in a 4-hour test, so I actually HAD to solve it... well, I almost did at the time

Also, for mapping (0,1) onto [0,1] with a continuous function:

0.5 * ( 1 + sin( x / ( 2*pi ) ) )

Back to my problem...

Anyone has any ideas? Maybe this could be done using the fact that IR is a Q-vectorial space of non-finite dimension?

[edited by - ToohrVyk on August 15, 2003 8:32:18 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
tu vas en prépa?
tu verras, c''est fun

No continuous function will satisfy your condition. Easy to prove.

if you want an easy function that will satisfy your condition, try this one :
f(x) = 1 if x is rational, 0 otherwise.

Share this post


Link to post
Share on other sites
Zipster    2359
quote:
if you want an easy function that will satisfy your condition, try this one :
f(x) = 1 if x is rational, 0 otherwise.

Gah, that''s what my Calculus professor would always say! Although it was more like, "between any two rational numbers there is an irrational number."

Share this post


Link to post
Share on other sites
janos    224
excuse me for my stupid post (anonymous)
I agree, finding such a function is not trivial

here''s my proposal for f

let x in [0,1].
x is written 0.x0x1x2x3... (any basis)
g(x) is the number written with the even placed digits of x
(eg : 0.x0x2x4...)
h(x) is the number written with the odd placed digits of x

if g(x) has an infinite number of non zero digits then f(x) = 1

otherwise f(x) = h(x) * 10^PlaceOfLastNonZeroDigits(g(x)) clamped to [0, 1]


Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
quote:
Original post by Zipster
Although it was more like, "between any two rational numbers there is an irrational number."

Also, between any two irrational numbers there is a rational number...

Share this post


Link to post
Share on other sites
Stonicus    157

mSeedBase[0] = 15731;
mSeedBase[1] = 789221;
mSeedBase[2] = 1073741824;
mSeedBase[3] = 0x7fffffff;
mSeedBase[4] = 1376312589;

float Noise::PRandom(int n)
{
n = (n << 13) ^ n;
return float(1.0 - ((n * (n * n * mSeed[0] + mSeed[1]) + mSeed[3]) & mSeed[4]) / float(mSeed[2]));
}


this is a simple pseudo random number generator I use to make my Perlin Noise.

Seed bases are just primes.

return values are clamped between -1 and 1.

Share this post


Link to post
Share on other sites
ToohrVyk    1595
Mais je suis déjà en prépa... c ma deuxième année l''année prochaine.

Janos: your solution works, nice one btw. Reminds me of that circle <-> disk bijection

Stonicus: I''m looking for a purely mathematical definition.

ToohrVyk

Share this post


Link to post
Share on other sites
janos    224
The Hausdorff-Banach-Tarsky paradox? fun!

Tu vois, la prépa ça m''a mené au final dans une boite de jeux vidéo. à l''époque on codait sur HP48 pendant les TD.

Share this post


Link to post
Share on other sites
janos    224
sorry, it was not the paradox I thought. The B-T-H paradow is much more complex and has to do with finitely many parts of the unit sphere isometrically displaced and connected to form a larger volume.

Share this post


Link to post
Share on other sites
ToohrVyk    1595
Nous, pendant les TD, on fait du Caml sur des Performa 450...

That disk<->sphere bijection is a paradox too, in that it turns a surface (the disk) into a curve (albeit a noncontinuous one).

ToohrVyk

Share this post


Link to post
Share on other sites
Cedric    158
Out of curisotiy, at what age are you expected to be able to do this kind of problem? I just finished my first year of university (19-20 years old), and this is pretty much my "upper limit", for the problems that I can do on my own (i.e.: without having learned the "trick" in class).

Cédric

Share this post


Link to post
Share on other sites
ToohrVyk    1595
I am 18 years old, but it got solved by a few people my age. It was aimed at an average of 19-20 years old (although this particular question was more about making out the hard-working students from the smart ones).

ToohrVyk

Share this post


Link to post
Share on other sites
Zipster    2359
quote:
Original post by Anonymous Poster
quote:
Original post by Zipster
Although it was more like, "between any two rational numbers there is an irrational number."

Also, between any two irrational numbers there is a rational number...


Well yes, that would be an implicit corollary

Share this post


Link to post
Share on other sites
Thr33d    382
I thought I read somewhere (probably isaic asimov''s "on numbers" book) that there were more irrational than rational numbers (a higher density of irrational numbers.)

But if ''between any two rational numbers there is an irrational number'' and the inverse is true, doesn''t that say that for then range of 0 -> largest irrational number < 1 the densities would be equal?

Could someone please clear this one up for me?


-Michael

Share this post


Link to post
Share on other sites
ToohrVyk    1595
Nope, that doesn''t mean the density is the same, because this theorem says "there is at least one" of each between two irrational numbers, it does not specify how many of each, or their densities.

Similarly, for each irrational number x , there exists an integer n so that n > x, and for each integer n there exists an irrational number x so that x > n. But IR \ Q is far more infinite than IN.

Where does the "more infinite" result come from? I don''t know the english version of the world, but it could be something like "countability". What the? Well, it means that you can count all elements in a set (that is, tie at least one number to each element) without forgetting any. A countable set is therefore less infinite than an uncountable set. We have two important results :

Q is countable ( 0 for 0, 1 for 1, 2 for -1, 3 for 1/2,4 for -1/2, 5 for 1/3, 6 for -1/3, 7 for 2/3...) : using that method you can tie one integer to each rational number.

IR is uncountable : suppose it was, and write each real number xn in [0,1] as the series of digits 0,xn1xn2xn3...

We therefore have a series of real numbers xn where n is an integer tied to xn. We can build the real y = 0,y1y2y3y4y5... where yk = 0 if xkk > 0 and yk = 1 if xkk = 0. This number has at least one digit of difference with ANY of the reals in the series xn. But since we counted all the elements in [0,1], and y is not in the series, y is not in that range. But IT IS! Therefore, IR is uncountable.

Since Q is countable and IR is uncountable, then IR\Q must be uncountable too (or we''d have a way to count IR), which means IR\Q is "more infinite" than Q.

ToohrVyk

Share this post


Link to post
Share on other sites
Stonicus    157
quote:
--------------------------------------------------------------------------------
Original post by Anonymous Poster

quote:
--------------------------------------------------------------------------------
Original post by Zipster
Although it was more like, "between any two rational numbers there is an irrational number."
--------------------------------------------------------------------------------


Also, between any two irrational numbers there is a rational number...



first states: R I R
second states: I R I

Also, between any two numbers is another number.

so take the first state:
R I R, is also:
R (I) I R - In these cases there is an R between the 2 I's
R I (I) R - ...R I (R) I R...

R (R) I R - These cases the number in between is R
R I (R) R

So between any two rational numbers is a rational number, and between any two irrationals is an irrational.

Whee!







[edited by - stonicus on August 22, 2003 3:51:20 PM]

Share this post


Link to post
Share on other sites
Stonicus    157
quote:
But IR \ Q is far more infinite than IN.


Hehe. "More Infinite" is a weird term, but pefectly legal.

Take the set of all Even Numbers and take the set of all Even Numbers Divisable By 5 (10, 20, 30... etc)

Both sets are infinite. However, the set all evens contains the entire set of (Evens / 5) plus some. So while both are infinite, between any non-infinite range, the set of all Evens will have more elements.

EDIT: I guess in the range of (9, 11), those two sets will have the same size (1).

[edited by - stonicus on August 22, 2003 3:52:46 PM]

Share this post


Link to post
Share on other sites