How Can We Make 100! Divisible by 12^{49}?

[whatta]

btw, on Pell equation. I wrote a brute force script (copy paste in html file),

<script>

// find solutions for x^2=ny^2 + 1 in integers for n > 0 by brute force
// this takes lots of time, so be patient and do not abuse task manager

limit = 1234567; // this is when do we stop wasting CPU cycles

for (n = 1; n < 10; n++) {

	x = 1;
	y = 1;

	i = 0;
	while (i++ < limit) {

		l = x * x;
		r = n * y * y + 1;

		if (l==r) {
			alert ("Solution: n="+n+", x="+x+", y="+y);
			break;
		}

		if (l > r) y++;
		if (l < r) x++;
	}

	if (x * x != n * y * y + 1)
		alert ("No solution was found for n="+n+" up to x="+x+", y="+y);
}

alert ("Nothing to wait for :(");

</script>

(edit:ah, I've found the flaw in my script (fixed above), now it actually finds something)

 

[TheDestroyer]

Well, since God is omnipotent, he's should have no problem to do the job with single cut, so your solution is only suboptimal. You should now spend the rest of your life looking for such a space transform that it only takes 1 cut in that space. The day when you find it, heavens will open and accept your enlightened soul.

Give me a break ! Did I say anything wrong? or only because I wrote the last sentense in capital mode?

I feeled that StatusX want to proof that there is situation that can destroy my way of solution, That's the reason !

Take it friendly, we are always friends, and must not care about things like this... even if I mistaken, you should pass :)

 

[whatta]

that was supposed to be a joke :/

 

[StatusX]

It looks like this got locked up again. Gibz, exactly what were you looking for? Solving pell's equation doesn't seem like a good brain teaser question, more of an ongoing research project.

And please don't answer a question unless you're willing to post a new one. I don't mean to take over this thread, but I'd like to see it get started again.

Here's another question. Prove that, except for the groups of order 1 and 2, every finite group has a non-trivial automorphism (ie, an isomorphism from the group to itself).

 

[sriperso]

answer to gokul's Question: 2/3
100! contains 98 2's and 49 3's.

 

[pki15]

Here's another question. Prove that, except for the groups of order 1 and 2, every finite group has a non-trivial automorphism (ie, an isomorphism from the group to itself).

Okay, suppose G is non-abelian. Let a,b \in G such that ab \not = ba. Then \phi (x) = axa^{-1} is the inner automorphism, and \phi(b) = aba^{-1} \not = b. So \phi is a nontrivial automorphism.

Now if G is abelian, G = Z_{p_1^{n_1}} \oplus Z_{p_2^{n_2}} \oplus \dots \oplus Z_{p_k^{n_k}} by the Fundamental Theorem of Finite Abelian Groups. But any automorphism of Z_{p_i^{n_i}} gives an automorphism of G, just apply the automorphism to the i-th component of G. But we know that sending a generator of Z_k to a different generator (i.e. any element relatively prime to k) gives a non-trivial automorphism. So as long as G has a component not Z_2, we're done.

So the only remaining case is G = Z_2 \oplus Z_2 \oplus \dots \oplus Z_2. Now there is an automorphism of Z_2 \oplus Z_2 that sends (1,0) to (0,1) and (0,1) to (1,0) and (1,1) to (1,1). Extend this to an automorphism of G by applying this automorphism to the first two components and leaving the rest of the components fixed.

This should take care of all the cases I think... Let me know if there's a flaw in the argument somewhere, I didn't check too carefully.

Here's another question:

Prove the 4-color theorem for all planar graphs with at most 12 vertices. (Obviously, don't apply the 4-color theorem or any of its equivalent statements) Also, don't waste your time coloring all such planar graphs, there's a nice argument.

 

[StatusX]

Yea, that's right pki, although for the middle case it's easier to just send elements to their inverses. By the way, does anyone know if this is also true for infinite groups? The only complication would come from non-finitely generated abelian groups where every element has order 2. If these were all isomorphic to an infinite direct product/sum of Z2's, it'd be easy, but I'm not sure they are.

 

[nugae]

A new question

I'm a bit confused about when you post a question here and when you start a new thread, so if anyone wants me to make a new thread out of this, just tell me and I'll do it!

I've been looking at the value N(n) of N that satisfies the equation

\sum_{1}^{n}(N-i)^{n}=N^{n}

Thus turns out to be

N(n)=1.5+\frac{n}{ln2}+O(1/n)

where the O(1/n) term is about 1/400n for n>10.

I've verified this by calculation up to about n=1000, using Lenstra's long integer package LIP.

This result is so beautiful and simple that it must be possible to prove it without brute-force calculation. If anyone has any suggestions as to how to begin then I'd be very grateful!

 

[krateesh]

New question !

What is largest possible value for n...when case is----

1000! / 10^n

 

[Gib Z]

Are you sure you put the question correctly? n can be arbitrarily large..

If your expression is for the largest value of that expression, its when n tends to negative infinity.

 

[krateesh]

i mean for what largest value of n we get a positive integral value as the quotient of these two...i think it has sometging to do with progressions...

 

[nugae]

I'm going to answer the question for 1000! / 5^n. You should be able to see that the answer is the same for 1000!/10^n.

Numbers from 1 to 1000 that are divisible by 5 each contribute a factor of 5 to 1000!. That gives us 1000/5 factors of 5 so far.

Numbers from 1 to 1000 that are divisible by 5² each contribute two factors of 5 to 1000!, which gives us 2×1000/5² factors of 5; but everything that is divisible by 5² is also divisible by 5, so all numbers divisible by 5² have already been counted once, which means that we only need to add 1000/5² to our original total of 1000/5.

Same reasoning for 5³: three factors, but we've counted two of them already, so we add 1000/5³ and get a total of 1000/5 + 1000/5² + 1000/5³.

Same reasoning for 5^4 (except that we have to remember to discard fractions, so that 1000/5^4 = 1 and not 1.6)... and then we can stop, because 5^5 > 1000.

So the total you want is

1000/5 + 1000/5² + 1000/5³ + 1000/5^4.

If you want the answer for 123456 rather than 1000, divide 123456 by 5 repeatedly, discarding the fractional part of each answer, until you get to 0, and then add together all the quotients you've calculated.

 

[krateesh]

but in case of 10 we have also got individuals...such as 2*5..4*5...

 

[Moo Of Doom]

Krateesh, for each 10 we have we must have a factor of 5 and a factor of 2. There are 500 even numbers less than 1000, so we have at least 500 factors of 2 (we have way more, actually), but there are only 249 factors of 5 (by nugae's formula) in 1000!. For each of those factors, we have a power of 2, and so we can divide 1000! by 10^249 and still get an integer. Dividing by 10 one more time, though, will result in a non-integer since we have no more factors of 5 in the resulting number.

 

[StatusX]

Browsing through some old threads I found https://www.physicsforums.com/showthread.php?t=119552" I had that I was never able to figure out. It seems pretty interesting. I'll work on it some more, but I thought I'd put it up here to get this going again:

Let R be a ring with the property that x³=x for all x. Prove that R is commutative. Does this generalize for x^k=x?

 

[morphism]

Ah... That's one of two infamous problems in Herstein. (The other being the lcm problem that appears early in the section on group theory. I forgot the actual statement though!)

Here's a relevant webpage. Don't look if you don't want to see the solution.

 

[Diffy]

Hi,

(first post!)

I really have enjoyed this thread. I have got to go back and think about all the problems posted. Some of them I really enjoyed spending time on.

Here is an interesting question (interesting to me, and hopefully to you) that I came up with as soon as I was first introduced to group theory. It started when in the first chapter of my book we were introduced to the group of symmetries of a square. One was to imagine taking a square out of a plane and all the different ways of putting it back in. This of course, defines the dihedral group of order 8.

Imagine all the ways a cube can taken out of a solid 3d space and put back in. Does this form a group the same way a square does? If so what is this group? What is its order?

 

[fantispug]

I proved SatusX's problem (for n=3) using a slightly different method (though it uses similar ideas it was developed independently):

a+b=(a+b)^3=a^3+b^3+a^2b+ab^2+b^2a+bab+aba
And
a-b=(a-b)^3=a^3-b^3-a^2b+ab^2-ba^2+bab-aba
Using a^3=a, b^3=b, and adding and subtracting the equations gives
a^2b+ba^2+aba=0
<br /> ab^2+b^2a+bab=0
This is more useful with a rearrangement:
a^2b=-(ba+ab)a
<br /> ab^2=-b(ba+ab)
Then
ab=a^3b=a(a^2b)=-a(ba+ab)a
<br /> ab=ab^3=(ab^2)b=-b(ba+ab)a
Using symmetry from the former equation
ba=-b(ab+ba)b=-b(ba+ab)a=ab
Generalising for any k is much harder via my method though.

 

[Alan J.]

How can one find the surface area of a ring?

 

[fantispug]

Imagine all the ways a cube can taken out of a solid 3d space and put back in. Does this form a group the same way a square does? If so what is this group? What is its order?

I assume we're just talking about rigid rotations here. Then it is a group:
Identity: Pick it up and put it back without changing it.

Associativity: This is intuitive, but I find it hard to argue. The groupings of the rotations don't matter. One way to see this is that any rotation in 3D space can be performed by multiplying the position vectors by a single 3x3 special orthogonal matrix. Matrices are associative, so all our rotations are associative.

Inverses: Just rotate the cube in the exact opposite way, this is always possible.

If we just turn the cube on the spot (as if it were a square) we get three operations;
r, r^2, r^3,r^4=I. (Take r=rotation clockwise for convenience).
Now we can pick up the whole cube and rotate it towards us. That gives
t,t^2,t^3,t^4=I.
Finally pick up the whole cube and turn it left:
l,l^2,l^3,l^4=I.

The total number of elements in the group, is the same as the total number of different orientations of the cube - for each face it is like a square confined to the plane, giving 4 orientations * 6 faces = 24 elements.

Now the three operations are not independent.
t=l.r.l^-1
r=t.l.t^-1
l=t.r^-1.t^-1

The multiplication table is too long to write out, however I believe the following is an isomorphism with S_4:
\phi(r)=(1234)
\phi(l)=(1423)
\phi(t)=(1243)

I would be interesting to see what happens if you included 4d rotations.

 

[JohannesKepler]

Math, although integral, is useless without the metaphysical ideas of Kepler, Leibniz, Kastner, Gauss, and Riemann. It is impossible to unerstand the causes of motion in the universe, through mathematical manipulations.

 

[kbaumen]

Here's a funny one, though rather simple. Sorry if it has been posted already.

a = 1, b = 1
a = b
a^{2} = ab
a^{2} - b^{2} = ab - b^{2}
(a + b)(a - b) = b(a - b)
a + b = b
1 + 1 = 1
2 = 1

Where is the flaw?

 

[sutupidmath]

Here's a funny one, though rather simple. Sorry if it has been posted already.

a = 1, b = 1
a = b
a^{2} = ab
a^{2} - b^{2} = ab - b^{2}
(a + b)(a - b) = b(a - b)
a + b = b
1 + 1 = 1
2 = 1

Where is the flaw?

since b=a=1 it implies that a-b=0, so u cannot acutally divide by a-b, since it is zero, and we all know that division by zero is not allowed, or not defined in the reals.

 

[sutupidmath]

here it goes

integ of dx/x, do it applying integraton by parts. what do u get?

 

[Gib Z]

We get I = 1 - I, which only seems problematic because in our notation we do not differentiate different indefinite integrals (ie indefinite integrals that differ by an additive constant). The constant on integration for the two different I's in the expression have different constants.

 

[Gib Z]

O well since I guess I got the last one, I'll just ask again what post 169 asked: How can one find the surface area of a ring?

 

[StatusX]

Here's one:

Let G be a group of odd order. Prove that for every element g in G, there is exactly one element h in G such that h²=g.

 

[rs1n]

Cute problem

I didn't read this entire thread, so this problem may have already been posted. It was a problem that got tossed around by graduate students, and I thought it was cute.

Suppose p(x) is a polynomial of degree d with nonnegative integer coefficients. You are allowed to evaluate p(x) at exactly TWO values of x. What two values do you use in order to completely determine the coefficients of p(x)?

 

[morphism]

Here's one:

Let G be a group of odd order. Prove that for every element g in G, there is exactly one element h in G such that h²=g.

Because |G| is odd, so too is o(g) for each g in G. Consequently, o(g^2)=o(g). This means that <g^2>=<g>, and do this for each g in G. [Alternatively, let o(g)=2k-1 so that g^(2k-1)=1 => (g^k)^2 = g.]

For uniqueness, let S={g^2 : g in G}, and note that |S|<=|G|. On the other hand, each element in G is a square, and all the squares in G come out of S, so that |G|<=|S|.

 

[morphism]

I didn't read this entire thread, so this problem may have already been posted. It was a problem that got tossed around by graduate students, and I thought it was cute.

Suppose p(x) is a polynomial of degree d with nonnegative integer coefficients. You are allowed to evaluate p(x) at exactly TWO values of x. What two values do you use in order to completely determine the coefficients of p(x)?

Hmm. Are there any restrictions on x, i.e. does it have to be a nonnegative integer? And can we use knowledge gathered from evaluating at the first value to pick the second one?

My initial guess was +/- 1, but that won't be sufficient most of the time. So maybe +/- 1/d, but this also doesn't seem to be very helpful for large degrees. It seems impossible to do it with two values picked at the same time!

 

[rs1n]

Hmm. Are there any restrictions on x, i.e. does it have to be a nonnegative integer? And can we use knowledge gathered from evaluating at the first value to pick the second one?

My initial guess was +/- 1, but that won't be sufficient most of the time. So maybe +/- 1/d, but this also doesn't seem to be very helpful for large degrees. It seems impossible to do it with two values picked at the same time!

There are no restrictions on x, other than x\in \mathbb{R}. And yes, you may use the information you obtained from one evaluation in your other evaluation of p(x). That is, if you evaluate at x=a, you may use the information obtained from p(a) to pick your second value of x.

 

[AKG]

I didn't read this entire thread, so this problem may have already been posted. It was a problem that got tossed around by graduate students, and I thought it was cute.

Suppose p(x) is a polynomial of degree d with nonnegative integer coefficients. You are allowed to evaluate p(x) at exactly TWO values of x. What two values do you use in order to completely determine the coefficients of p(x)?

Has something to do with the d^th root of something like, I dunno, 2. Or maybe a better one to do is this: first evaluate p(1), that's the sum of all the coefficients. Then pick a prime P > p(1), and evaluate p(P). Then if you consider p(P) mod P², p(P) mod P³, ..., p(P) mod P^d or something you can recover the coefficients.

 

[rs1n]

Or maybe a better one to do is this: first evaluate p(1), that's the sum of all the coefficients. Then pick a prime P > p(1), and evaluate p(P). Then if you consider p(P) mod P², p(P) mod P³, ..., p(P) mod P^d or something you can recover the coefficients.

That's essentially it, but there's still some extra math required if you pick a prime. Instead, let n=\lceil \log_{10} p(1) \rceil. Then evaluate p(10^n). The k-th coefficient can be recovered by simply reading off the k-th block of n digits.

Example:

p(x) = 99 x^2 + 23.
p(1) = 99+23 = 122.
n = 3

p(1000) = 99 (1000)^2 + 23 = 099, 000, 023

 

[gel]

Surely a single evaluation of p(x) will do. Just take x to be any transcendental number. Eg, x=e. Of course, restricting to integer x is more interesting.

 

[Poseidon]

Are you sure you guys weren't one of the sources used in "An Introduction to Criminalistics?"

 

[greenlight22]

I know.

 

[lwasmund]

We could all just try to fingure out what pi really is.

 

[StatusX]

Some of you might have seen this before, but I just found it, and it has such a nice solution I thought I'd post it:

Say we have N people, and we have a door we want to lock in such a way that at least M of the people must be present in order for it be unlocked. To do this, we use some number L of locks and distribute keys to each of the people, so that when any M of them are present, they have all the keys among them, but for a group of fewer than M, some keys will be missing. What's the best way to do this (ie, the minimal L)?

I'll post the solution in a few days if no one else does.

 

[gel]

Cool question

Spoiler

N choose (M-1). For every subset of M-1 people there must be a key belonging to everyone except them

Easy once you spot the trick.

 

[StatusX]

That's right. Were you able to prove that's the optimal solution, ie, has the least number of locks and keys?

 

[StatusX]

Here's the proof, if anyone's interested:

Spoiler

Pick some group of M-1 people. This group must be missing the key to at least one lock. But since the addition of anyone else gives them the necessary M people, anyone outside the group must have the keys to all their missing locks. In particular, each person either has all or none of the keys to this set of locks, so if there's more than one, we might as well consolidate them into a single lock.

Thus we have a map from the set of M-1 person subsets (a set with N choose M-1 elements) to the set of locks. We show it's a bijection. If it wasn't injective, and two M-1 person subsets were missing the same lock, then their union, a group of at least M people, would also be missing the lock, a contradiction. If it wasn't surjective, there would be locks that no M-1 person group is missing, but then we clearly don't need these locks.

Thus an optimal solution has N choose M-1 locks, with one lock for each M-1 person group, and with the people in the group being precisely the people who don't have the key to the corresponding lock.

 

[maze]

Since no-one has posted a new question in over a month, here's a cool one I saw somewhere:

In a very long hallway, there are 1000 doors all initially open. Consider the following process:
First, you close every door.
Second, you open every other door.
Next, you toggle the state of every 3rd door (open it if it is closed and close it if it is open),
Next, you toggle every 4th door,
and you continue this process, toggling the state of every nth door.

At the end of this process (when n=1000), how many doors are open?

Here is a diagram:
http://img504.imageshack.us/img504/1967/door2rc2.gif

 

[tim_lou]

maze's question is classic... the answer is

Spoiler

N-floor (sqrt(N))
the nice animation makes it kinda obvious... the reason is only perfect squares have an odd number of distinct divisors.

problem 2 above

Spoiler

it suffices to find # of ways to arrange coins such that each row has one coin. This is easily given as n^n, so answer is 1-n^n/ \binom{n^2}{n}... if you want to find probability such that at least one row or one column has no silver coin, then it would be 1-n!/ \binom{n^2}{n}

problem 3 above

Spoiler

LHS is less than or equal to a(a+b+c)+b(a+b+c)+c(a+b+c) by weighted AM-GM inequality, which is clearly less than or equal to 1

Problem 1 seems too long and I am feeling kinda lazy...

Now for my problem... hmmmm... after all these years... let's see...I'm not sure if this is appropriate:

prove that all one dimensional compact connected Lie group (a manifold that is also a group with smooth multiplication) is diffeo-isomorphic to S1 (the circle).

In case we want to make things "elementary", evaluate:
\int_{0}^\infty \frac{dx}{1+x^n}
In case you think a simple contour will bring this problem down... try to evaluate it for n>1, not just integers.edit: sorry, latex just doesn't work well with spoiler alerts...

 

[qntty]

I wasn't able to solve the following problem when I came across it, if anyone wants to give it a shot:

18 people play in a tournament that has 17 rounds of 9 games. Each person plays in only one game in each of the rounds and plays every other person no more than once in the tournament. After n rounds there are 4 people who have only played one game, what is the largest possible n?

 

[Gib Z]

For tim's integral:

Spoiler

Its simply differentiating the integral with respect to n. We get that I'(n) = -1, so that I(n)= -n + C. The constant is evaluated by letting n=2, where we find that I(2) = pi/2.

Hence, pi/2 = -2 + C, C = 2 + pi/2

I(n) = -n + 2 + pi/2

 

[tim_lou]

I don't think differentiating with respect to n helps... you'll get something like x^n (ln x) on top, and it's not obvious to me how you manage to simplify it to get one.

Also, the answer should always be positive, so you can't have -n there.

 

[Gib Z]

Sigh. I am still kicking myself for differentiating wrt x and not n. Sorry for wasting everyones time.

 

[tim_lou]

oops.. it's been a while and I completely forgot about this thread... I feel that I should provide a solution at least...

since spoiler doesn't work with latex... close your eyes if you don't want to see the answer!

let
\frac{1}{1+x^n}=\int_0^\infty e^{-(1+x^n)t}dt

the integral becomes
\int_0^\infty\int_0^\infty e^{-(1+x^n)t} dxdt

but, using integration by parts
\int_0^\infty e^{-x^n t}dx=\int_0^\infty tnx^n e^{-x^n t} dx=t^{-\frac{1}{n}}\Gamma \left(1+\frac{1}{n}\right)

You might complain that t is singular at 0... but the integral converges just fine as long as t>1.

at the end of the day we get:
\int_{0}^\infty \frac{dx}{1+x^n}=\Gamma\left( 1-\frac{1}{n}\right)\Gamma\left(1+\frac{1}{n}\right)
neat, heh?

You could simplify this to
\frac{\pi}{n \sin(\pi/n)}

In fact... you could evaluate this integral using a wedge in the complex plane and get directly the sin result.

 

[qntty]

Tim hasn't given a problem and it's been a long time so I'll revive it.

Given that
<br /> \int_{- \infty}^{\infty}{e^{-x^2}} dx = \sqrt{\pi}<br />
find (for t>0)
<br /> \frac{d}{dt} \int_{- \infty}^{\infty}{e^{-tx^2}} dx<br />

 

[Ignea_unda]

Okay new to this, and with my luck probably wrong but...

Spoiler

inside the integral we have exp[-tx^2] = exp[t]exp[-x^2]

Spoiler

We can then pull exp[t] out of the integral and evaluate the integral

Spoiler

Finally we take the derivative and multiply the two together getting sqrt(pi)*exp[t]