wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Find a Function
        
(Message started by: THUDandBLUNDER on Nov 4^th, 2003, 10:44am)

Title: Find a Function
Post by THUDandBLUNDER on Nov 4^th, 2003, 10:44am

Find a function F: N⁺ -> N⁺ such that

(i) if x < y then F(x) < F(y)

(ii) F(yF(x)) = x²F(xy)

Title: Re: Find a Function
Post by towr on Nov 4^th, 2003, 11:33am

::[hide]quite a usefull function for making lenses and mirrors for telescopes..[/hide]:: :P

Title: Re: Find a Function
Post by THUDandBLUNDER on Nov 4^th, 2003, 9:48pm

:[hide]Don't see how it concerns my refractor telescope. Or my contact lenses.[/hide] :P

Title: Re: Find a Function
Post by towr on Nov 5^th, 2003, 12:58am

I don't know about the first (because the term doesn't ring a bell), but it does concern the second.. (though that get's a lot more complecated by other considerations as well)

Title: Re: Find a Function
Post by Eigenray on Nov 5^th, 2003, 2:33am

If F is a polynomial, condition (i) is extraneous (there is still a unique solution without it), so should we be looking for non-polynomial solutions?

Title: Re: Find a Function
Post by Dudidu on Nov 5^th, 2003, 3:17am

Can anyone tell me what is wrong with this solution (if it is wrong) ???:
[hide] F(n) = n².

Quote:

function F: N⁺ -> N⁺

The suggested F fulfills this condition.

Quote:

if x < y then F(x) < F(y)

The suggested F fulfills this condition since ² is strictly monotonically increasing when n[in]N⁺.

Quote:

F(yF(x)) = x²F(xy)

The suggested F fulfills this condition since F(yF(x)) = F (yx²) = y²x⁴ and x²F(xy) = x²x²y² = y²x⁴.
[/hide]

Title: Re: Find a Function
Post by THUDandBLUNDER on Nov 5^th, 2003, 3:26am

Quote:

Can anyone tell me what is wrong with this solution

I don't see a solution. Only an answer. :D

on 11/05/03 at 02:33:42, Eigenray wrote:

If F is a polynomial, condition (i) is extraneous

Condition (i) is used in condition (ii) to arrive at a solution.

Title: Re: Find a Function
Post by Eigenray on Nov 5^th, 2003, 8:15am

on 11/05/03 at 03:26:52, THUDandBLUNDER wrote:

Condition (i) is used in condition (ii) to arrive at a solution.

I don't believe there are any polynomials F : N⁺ -> N⁺ that satisfy (ii) but not (i). Since you bothered to include (i) as a condition, it suggests to me that there are nonpolynomial solutions to (ii), but not (i), which should be excluded from the nonpolynomial solutions to (ii) that we should perhaps be trying to find, if that was your intention when asking this question. Or, more likely, including (i) makes the solution unique.

Is [hide]F(x)=x²[/hide] the only solution? So far I've figured out that you must have [hide]F(2^k) = 4^k[/hide], so it seems likely.

Edit: What I mean is that since the problem asked for a solution, (i) is irrelevent, unless we're looking for all solutions.

Title: Re: Find a Function
Post by Icarus on Nov 5^th, 2003, 10:06am

Functional equations such as (ii) often have a finite number (usually 1) of continuous solutions, but also have an infinite number of discontinuous ones. Whether this is the case for (ii) itself, I don't know. But in order for the solution to be unique, you generally have to give a second condition, such as "F is continuous" or "F is a polynomial" or "F is strictly increasing".

I do not see why either of the first two would be preferable to the third in the statement of the problem. In particular, "F is a polynomial" gives a considerable amount of additional information which I doubt is needed to obtain uniqueness - thereby weakening the final result.

Title: Re: Find a Function
Post by THUDandBLUNDER on Nov 6^th, 2003, 3:32am

Quote:

But in order for the solution to be unique, you generally have to give a second condition, such as "F is continuous" or "F is a polynomial" or "F is strictly increasing".

Or, as in this case, "F is one-to-one".

Title: Re: Find a Function
Post by Icarus on Nov 6^th, 2003, 9:57am

on 11/04/03 at 10:44:21, THUDandBLUNDER wrote:

i) if x < y then F(x) < F(y)

This would be "F is strictly increasing" - much stronger than "one-to-one".

Title: Re: Find a Function
Post by THUDandBLUNDER on Feb 29^th, 2004, 5:07am

Solution:
[hide] We have the conditions
(i) If x < y then F(x) < F(y)
(ii) F(yF(x)) = x²F(xy)

(i) implies that F is one-to-one.

Putting x = 1 in (ii) we get
F(yF(1)) = F(y)
If F(1) > 1 then condition 1 is violated.
So F(1) = 1

Now putting y = 1 in (ii) we get
(iii) F(F(x)) = x²F(x)

By applying condition (ii) twice we get
F(F(x)F(y)) = y²F(yF(x)) = y²x²F(xy) = (xy)²F(xy)

Hence
(iv) F(F(x)F(y)) = (xy)²F(xy)

In (iv) replacing xy with x and 1 with y we get
F(F(xy)) is also equal to (xy)²F(xy)

But since F is one-to-one we have that
(v) F(x)F(y) = F(xy)

Hence
(a) F(F(x)) = x²F(x)
(b) F(x)F(y) = F(xy)

Now suppose F(x) > x² for some x
Then
F(F(x)) > F(x²) = F(x)F(x)
That is
x²F(x) > F(x)F(x)
which means
x² > F(x)
which contradicts F(x) > x²

A similar contradiction arises by assuming F(x) < x²
Therefore we must have that
F(x) = x² for all x
[/hide]

Title: Re: Find a Function
Post by MatrixFrog on Mar 26^th, 2004, 8:13pm

on 11/04/03 at 21:48:30, THUDandBLUNDER wrote:

:[hide]Don't see how it concerns my refractor telescope. Or my contact lenses.[/hide] :P

[hide]y=x² is an equation for a parabola. there is a particular point for every parabola, called the "focus"... if you put a light source at the focus of a parabolic mirror, every ray of light will end up reflecting off the parabola and moving parallel to the axis of symmetry... http://www.cut-the-knot.org/Curriculum/Geometry/ParabolaMirror.shtml[/hide]

i meant to hide this, but my coding was a failure... sorry

Title: Re: Find a Function
Post by THUDandBLUNDER on Mar 26^th, 2004, 11:01pm

Quote:

y=x2 is an equation for a parabola. there is a particular point for every parabola, called the "focus"... if you put a light source at the focus of a parabolic mirror, every ray of light will end up reflecting off the parabola and moving parallel to the axis of symmetry...

I mentioned refractor telescopes, not parabolic reflectors.

Title: Re: Find a Function
Post by Icarus on Mar 27^th, 2004, 6:47am

I believe parabolic surfaces are preferable for lenses as well as for mirrors. The reason we usually use spherical surfaces is that they are much easier to produce. But with any spherical lens or mirror, you get "spherical aberation" - the failure of light to focus on a single point, causing the image to be slightly blurry.