Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

## #1 Re: Help Me ! » Function » 2013-05-18 14:22:21

I'm going to assume that f is a real valued function (not that it really matters).

It's easy to check that for any real number a, the function f(x) = x^2 + ax is a solution. I will show that these are the only continuous solutions.

Let g(x) = f(x) - x^2. Then g(x+y) = g(x) + g(y) and g(0) = 0.
Also 0 = g(0) = g(x) + g(-x), so g(-x) = -g(x) for all real x.

Let a = g(1).
We can prove by induction that g(nx) = ng(x) for all positive integers n and real x, and then we can deduce that g(x/n) = g(x)/n for all positive integers n and real x.
It follows that g(rx) = rg(x) for all rational r and real x, and so in particular g(r) = rg(1) = ar for all rational r.

If f is continuous then g is also continuous and so g(x) = ax for all real x.

## #2 Re: Help Me ! » Chebyshev's Inequality » 2013-02-21 15:47:54

White_Owl,

Suppose you wanted to find

Hopefully it is obvious that

exactly when
or
or
,

so

Similarly, you have observed that

exactly when
or
,

so

What anonimnystefy is referring to in post #6 is that

where
if
is true and 0 if it is false.
This is also equal to

I hope this helps.

## #3 Re: Help Me ! » A few questions » 2012-12-03 16:56:35

bobbym, I apologise if I have caused any offence but I think you are missing something.

Here are two statements:

(1) If k,m,n are positive integers and a = km(m+n), b = kn(m+n), c = kmn, then 1/a + 1/b = 1/c.

(2) If a,b,c are positive integers and 1/a + 1/b = 1/c, then there exist positive integers k,m,n such that a = km(m+n), b = kn(m+n), c = kmn.

In post #8 you demonstrate that (1) is true, but in order to solve Agnishom's problem you are using that (2) is true. Hopefully it is clear that (1) does not imply (2).

## #4 Re: Help Me ! » A few questions » 2012-12-03 13:37:57

I agree with bobbym that you don't need to reprove a result every time you want to use it, but if someone wants to use a result that you have never seen before and doesn't provide a proof of it then it is reasonable to be unhappy with the result, as Agnishom is.

Suppose that

where a, b, c are positive integers such that gcd(a,b,c) = 1.

Let  l = gcd(a,b),   m = gcd(a,c),   n = gcd(b,c)

Since gcd(a,b,c) = 1, it follows that gcd(l,m) = gcd(l,n) = gcd(m,n) = 1 and so there exist positive integers a', b', c' such that

a = lma'      b = lnb'      c = mnc'

Also gcd(a', b') = gcd(a', c') = gcd(b', c') = gcd(a', n) = gcd(b', m) = gcd(c', l) = 1.

Now if we substitute our expressions for a, b, c into the original equation we obtain

Since gcd(c', la'b') = 1, it follows that c' = 1, and hence ma' +nb' = la'b'.

Also gcd(a', nb') = gcd(b', ma') = 1, so a' = b' = 1 and so l = m + n.

Therefore   a = m(m+n),    b = n(m+n),    c = mn.

Of course we also have that gcd(m,n) = 1, but we don't need to use this to see that  a + b = (m + n)^2.

## #5 Re: Help Me ! » Abstract algebra question (homomorphisms) » 2012-02-16 15:39:33

A homomorphism h from Zm to Zn is onto if and only if h(1) generates Zn, or equivalently when the order of h(1) is n.
Since the order of h(1) must be a divisor of gcd(m,n), there can only be an onto homomorphism from Zm to Zn if n is a divisor of m.
If n is a divisor of m, then the number of onto homomorphisms is phi(n).

## #6 Re: Help Me ! » Number-theory problem (from another forum) » 2011-06-15 12:04:00

The first two congruences are equivalent to

.

17n-1 and 17m+1 cannot be 0 so we have

and
.

Hence if

then

and if
then
.

Now suppose that |m| > 17 and |n| > 17.
It follows from the two congruences above that

so
.

17n-17m-1 cannot be 0 so we have

so

and hence
.

Since |m|-17 and |n|-17 are both positive integers it follows that

and similarly
.

Therefore if (m,n) is a solution to these congruences then |m| and |n| are both at most 307
and so the bobbym's brute force search has found all of the solutions.

## #9 Re: Help Me ! » Clarification needed: p-primary components of an Abelian group » 2010-12-06 08:39:27

Are you sure that the theorem is not restricted to finite abelian groups G?
If this is the case, then for every prime p that does not divide the order of G, the p-primary component Gp will be trivial.
Hence, we need only take the direct sum over the finitely many p that divide the order of G.

If G is an infinite cyclic group, then Gp is trivial for all primes p, and so G is not a direct sum of p-primary components of G.

is also clearly not a finite direct sum of p-primary components.

## #10 Re: Help Me ! » Combinatorics and unique pairs with a twist » 2010-10-27 09:49:13

Hi jngrim,

I think you are miscounting something here.
12,13,14,15
23,24,25
34,35
46
56
you have used four 5s, 15,25,35,56 and two 6s 46, 56 so you only have (6,6) left over.

You could change your numbers slightly to
12,13,14,16
23,25,26
34,35
45,46
56
and use all of the numbers available.
I could have constructed this by taking a set of pairs that uses each number once 15,24,36, and then taking all of the other pairs.

It's not entirely clear to me how you want to generalise this problem, but here is one way.
Let S(n,k) be the maximum size of a set of pairs of numbers 1,2,...,n with the property that each number is used at most k times.
It is easy to see that

all of which attain the upper bound

I'll have to think a little more to see if this upper bound can always be attained.

## #11 Re: Help Me ! » Graph Theory - bipartite related proof » 2010-09-16 11:28:01

Hi cxc001

If you want to use induction, here's how I would go about it.

First I would construct a simple bipartite graph with n vertices and [n^2/4] edges, for each n.
You should be able to see how to do this by looking at the small cases. In the case n=1, the graph with one vertex and no edges is a simple bipartite graph.
This shows that P(n) >= [n^2/4].

Then I would show by induction that P(n) <= [n^2/4].
You've already done some base cases.
Suppose that n >=4 and that G is a simple bipartite graph with n vertices.
First show that G has a vertex with degree at most [n/2].
Then show that [(n-1)^2/4] + [n/2] <= [n^2/4]. This part is a little delicate. You may find it easier to split into two parts depending on whether n is even or odd.

## #12 Re: Help Me ! » equivalence relation questions » 2010-09-06 14:51:09

Hi nha,

A binary relation R on a set X is usually considered to be a set of ordered pairs of elements of X, so that the pair (x,y) is in the set if and only if xRy is true.
An equivalence relation on X is a binary relation on X so corresponds to a set of ordered pairs.

If E is a equivalence relation on X then the equivalence classes of E form a partition of X.
Conversely, if we have a partition of X then we can define a relation E on X by xEy if x and y belong to the same part of the partition. Then E is an equivalence relation on X.

In fact, there is a one-to-one correspondence between the equivalence relations on X and the partitions of X.

The ordered pairs corresponding to the partition {a,c,e,g,j},{f},{b,d,h},{i} are
(a,a), (a,c), (a,e), (a,g), (a,j),
(c,a), (c,c), (c,e), (c,g), (c,j),
(e,a), (e,c), (e,e), (e,g), (e,j),
(g,a), (g,c), (g,e), (g,g), (g,j),
(j,a), (j,c), (j,e), (j,g), (j,j),
(f,f),
(b,b), (b,d), (b,h),
(d,b), (d,d), (d,h),
(h,b), (h,d), (h,h),
(i,i).

## #13 Re: Help Me ! » group theory problem » 2010-09-05 11:05:24

Hi wintersolstice,

If I understand what you are doing correctly you are taking the set of all x=1,2,...,n-1 such that HCF(x,n)=r.
I think the condition you want on n and r is that HCF(r^2,n) = r.

To find the identity you need to solve the system of congruences

Since HCF(r^2, n) = r, we also have HCF(r, n/r) = 1 and so there is a unique solution modulo n.

## #14 Re: Puzzles and Games » 3 U's » 2010-08-29 10:02:34

I had thought that such words would be ubiquitous, but my search has proved unfruitful and now I am feeling rather lugubrious.

I assure you that I am scrupulous, and will resent any accusation that I have been untruthful.

## #15 Re: Help Me ! » Boxes of Arrows » 2010-08-15 11:11:58

I would usually use Burnside's lemma to count such things.

In the first example we are letting the rotation group of the square act on the drawings. This group has four elements: the identity, the quarter-turn clockwise, the quarter-turn anticlockwise, and the half-turn.

The identity fixes all of the 256 drawings.
The quarter-turns each fix 4 drawings.
The half-turn fixes 16 drawings.

Hence the number of different drawings if two are considered the same if one is a rotation of the other is
(256+4+4+16)/4 = 70.

If we also want to allow reflections then there are four more elements in our group: the two reflections in the diagonals of the square, the reflection in the vertical line through the centre of the square, and the reflection in the horizontal line through the centre of the square.

The two diagonal reflections don't fix any of the drawings.
The reflections in the vertical and horizontal lines each fix 16 drawings.

Hence the number of different drawings if reflections and rotations are considered the same is
(256+4+4+16+0+0+16+16)/8 = 39.
I notice that this is not the same as what John counted.

The 2x2x2 cube could be handled similarly, but I don't really have the time to do it right now.

## #16 Re: Help Me ! » Composite Functions » 2010-06-15 10:25:15

Articles on Wikipedia do not have owners. If anyone can edit an article then obviously anyone can edit the article to return it to an earlier state.

The threshold for inclusion in Wikipedia is verifiability, not truth. It doesn't matter whether or not what you wrote is correct; the reader should be able to verify statements made in the article by consulting the
reliable sources given for them.

## #17 Re: Help Me ! » Expected Value of Geometric random variable » 2010-05-10 09:37:40

As far as I can tell you want to use the formula

(which is valid for a random variable X that takes only non-negative integer values) to compute the expected value of a Geometric random variable.

In order to compute

you could use that

but I think it's just as easy to use

## #18 Re: Puzzles and Games » Please Explain... » 2010-04-05 23:43:28

When you replace numbers by their digit sums and cast out nines you are essentially considering two numbers to be the same if they have the same remainder when divided by 9.

I would write
rather that
when I am doing this. Hence we have

We cannot now deduce that

since 0 has three square roots modulo 9. These are 0, 3 and 6 so we have

and since I'm biased against negative numbers

## #19 Re: Puzzles and Games » Please Explain... » 2010-04-05 16:47:56

ZHero,

You haven't really shown that (N+2)^2 = 0, only that (N+2)^2 is divisible by 9.
Hence N must be one of 1,4,7 and you'll have to do something else to decide which.

## #20 Re: Help Me ! » integration by different parts » 2009-12-15 08:57:15

You have made a mistake in the second one.

If

then

If you correct this you will show that

## #21 Re: Help Me ! » A tricky integral » 2009-12-09 09:30:24

I get that

Your solution is correct. In fact

and

## #22 Re: Help Me ! » expectation of standard normal random variable » 2009-11-25 09:05:52

If
has the standard normal distribution then

which doesn't contain what I would call a double exponential (i.e. something like
).
Is this the integral that you are having problems with?

## #23 Re: Help Me ! » Real analysis question involving closures and unions » 2009-11-11 09:45:41

The order of quantifiers is important.

betterthangauss wrote:

Therefore, for any neighborhood
of
, there is an integer
,
, such that

This is true but the value of
many depend of the neighbourhood
.

What you want to show is the there exists an integer
such that for any neighbourhood of
of

## #24 Re: Puzzles and Games » A test problem... » 2009-11-11 09:08:58

In order to satisfy the condition that no set of four teachers has all of the answers but every set of five does we must have that for any set S of four teachers there is a question Q_S such that the four teachers in S don't have the answer to Q_S but the other six all do.

If S and T are two sets of four teachers and Q_S = Q_T then we must have S = T since S is the set of teachers who don't have the answer to Q_S and T is the set of teachers who don't have the answer to Q_T. Therefore we must have at least as many questions are there are sets of four teachers.

## #25 Re: Help Me ! » Epsilon Delta Proof » 2009-11-03 14:17:55

You could use any number in the interval (0, 1/3) in the place of 1/6. I believe the book chooses 1/6 because it is the midpoint of this interval.
You are right about why we need to bound x away from 0.

In the second problem we have that

for all
i.e. the domain of the square root function. Note that this function is not unbounded close to 0.

If you define limits for functions only defined on a subset of the real numbers like Wikipedia does, then we only need that

whenever
and
so demanding that
is unnecessary.
Of course you can always make
smaller if you want to.