Author |
Topic: An All Possible Function Puzzle (Read 441 times) |
|
K Sengupta
Senior Riddler
Gender:
Posts: 371
|
|
An All Possible Function Puzzle
« on: May 30th, 2006, 9:20am » |
Quote Modify
|
Determine all possible functions g:Z->Zsuch that: g(m-n+g(n)) = g(m) + g(n) for all m,n (- Z
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: An All Possible Function Puzzle
« Reply #1 on: May 30th, 2006, 11:46am » |
Quote Modify
|
I wonder, are there any solutions apart from the two trivial ones: g(n) = 0 and g(n) = 2n ?
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: An All Possible Function Puzzle
« Reply #2 on: May 30th, 2006, 3:01pm » |
Quote Modify
|
Anyway, it is quite easy to conclude that g(0)=0.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: An All Possible Function Puzzle
« Reply #3 on: May 30th, 2006, 3:27pm » |
Quote Modify
|
on May 30th, 2006, 11:46am, JocK wrote:I wonder, are there any solutions apart from the two trivial ones |
| No, I believe not. Consider only those values where m = n; we have g(g(n)) = 2g(n), leading directly to both trivial solutions. And since the domain of g is Z, the range of g must be either 0 or Z as well. --SMQ
|
|
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: An All Possible Function Puzzle
« Reply #4 on: May 30th, 2006, 6:00pm » |
Quote Modify
|
on May 30th, 2006, 3:27pm, SMQ wrote:And since the domain of g is Z, the range of g must be either 0 or Z as well. |
| I think it's a bit more subtle than that. Let I = { x | g(x) = 0}, and J = { x | g(x) = 2x }. I claim these are both ideals/subgroups/submodules of Z. (0) If y=g(x) is in the range of g, then g(y)=2y. (1) g(0)=0, by taking m=0, n=g(0). (2) If x=g(x), then g(x) = gg(x) = 2g(x), so x=g(x)=0. (3) If g(m)=2m, then g(-m) = -2m: take n=-m, and apply (2) to x=2m+g(-m). (4) If g(m)=2m, and g(n)=2n, then g(m+n)=2(m+n). (5) If g(m)=g(n)=0, then g(m-n)=0. It follows from (1) and (5) that I is an ideal, and by (1), (3), (4), J is an ideal. In particular, if x is in I, and y is in J, then xy is in both I and J, so xy=0. Thus either I={0} or J={0}. First suppose J={0}. Since J contains the range of g, it follows g(x) = 0 for all x. So assume I={0}. Taking m = -g(n), we have g(-n) = g(-g(n)) + g(n). By (0) and (3), g(-g(n))=-2g(n), and it follows g(-n) = -g(n). Finally, taking m=-n, we have g(-2n + g(n)) = g(-n) + g(n) = 0; since I={0}, we have g(n)=2n.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: An All Possible Function Puzzle
« Reply #5 on: May 30th, 2006, 7:41pm » |
Quote Modify
|
I haven't taken it very far, but it might prove easier to deal with h(n) = g(n) - n. The functional equation for h takes the nicely symmetric form h(m + h(n)) = h(m) + n.
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: An All Possible Function Puzzle
« Reply #6 on: May 30th, 2006, 7:58pm » |
Quote Modify
|
on May 30th, 2006, 6:00pm, Eigenray wrote:I think it's a bit more subtle than that. |
| It may indeed be more subtle than I stated (and JocK implied) -- I don't claim to know much of the formalism of analysis -- but you still seem to have come to the same conclusion. --SMQ
|
|
IP Logged |
--SMQ
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: An All Possible Function Puzzle
« Reply #7 on: May 31st, 2006, 7:00pm » |
Quote Modify
|
on May 30th, 2006, 7:58pm, SMQ wrote: It may indeed be more subtle than I stated (and JocK implied) -- I don't claim to know much of the formalism of analysis -- but you still seem to have come to the same conclusion. |
| That doesn't exonerate you. As anyone who has taught mathematics knows, it is very easy to come up with the right answer for all the wrong reasons. While it is true that the range of g is 0 or Z, this does not follow simply from the domain of g being Z. ----------------------------------------------------------------- Having some time to kill tonight I played around with the h(n) = g(n) - n substitution, and found that I was correct about it being easier to handle. Since Eigenray has already given a fine solution to this problem, I will give my approach under the guise of a generalization: If G is a group and h: G --> G, then h satisfies the condition h(xh(y)) = h(x)y for all x, y ( G if and only if h is an automorphism with h2 = I. Proof: Assume that the condition holds. If x = y = e, we get h(h(e)) = h(e). If x=e and y = h(e), then h(h(h(e))) = [h(e)]2, or h(e) = [h(e)]2. So h(e) = e. If x = e, h(h(y))=y. So h2 = I. if x = h(z), h(y + z) = h(y + h2(z)) = h(y) + h(z), so h is a morphism. Since h-1 = h, it is an automorphism. The other direction is obvious. If we apply this to h = g - I on Z, and note that the only automorphisms on Z with h2 = I are I and -I, it follows that g = 0 or g = 2I. Note that this applies not just to Z, but to all subgroups of R. If you want additional solutions, you need to find a group with additional nil-square automorphisms. For instance, if we replace Z with the Gaussian Integers, we also have the solutions g = I + C and g = I - C, where C is complex conjugation.
|
« Last Edit: May 31st, 2006, 7:44pm by Icarus » |
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: An All Possible Function Puzzle
« Reply #8 on: Jun 1st, 2006, 3:18am » |
Quote Modify
|
on May 31st, 2006, 7:00pm, Icarus wrote:That doesn't exonerate you. As anyone who has taught mathematics knows, it is very easy to come up with the right answer for all the wrong reasons. |
| ...hence the wink. My answer "felt right," but I'm fully aware how little that can actually mean. Props to you and Eigenray for your much more thorough and innovative solutions! Wasn't it Richard Feynman who said something along the lines of "every problem has at least one solution which is simple, elegant, intuitively obvious, and wrong." --SMQ
|
|
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: An All Possible Function Puzzle
« Reply #9 on: Jun 1st, 2006, 2:57pm » |
Quote Modify
|
on May 31st, 2006, 7:00pm, Icarus wrote:While it is true that the range of g is 0 or Z |
| Actually, it's not Quote:If we apply this to h = g - I on Z, and note that the only automorphisms on Z with h2 = I are I and -I, it follows that g = 0 or g = 2I. |
| Very nice indeed! Quote: Note that this applies not just to Z, but to all subgroups of R. |
| It does apply to Q, but not to any group isomorphic to G2 for any group G, for example (since we have h(x,y)=(y,x)). Hence g(x+ye) = (x+y)(1+e) satisfies the functional equation for all m,n in { x + ye : x,y in Z }, a subgroup of R. And R is isomorphic to R2 (as abelian groups): let { vi, wi : i < |R| } be a vector space basis of R over Q. Then h([sum]aivi + [sum]biwi) := [sum]bivi + [sum]aiwi is an order-2 automorphism of R, so g(x) = h(x)+x satisfies the functional equation for all x,y in R. Quote:For instance, if we replace Z with the Gaussian Integers, we also have the solutions g = I + C and g = I - C, where C is complex conjugation. |
| In fact there are infinitely many: Aut(Z2) = GL2(Z), and so for any integers with bc=1-a2, [ a b ] [ c -a ] also has order 2.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: An All Possible Function Puzzle
« Reply #10 on: Jun 1st, 2006, 3:34pm » |
Quote Modify
|
Crud. I forgot: It is only the continuous automorphisms of R that must have the form h(x) = ax.
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
|