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

[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
$\int_{- \infty}^{\infty}{e^{-x^2}} dx = \sqrt{\pi}$
find (for t>0)
$\frac{d}{dt} \int_{- \infty}^{\infty}{e^{-tx^2}} dx$

 

[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]

 

[ThirstyDog]

I will have a guess and I think it goes something like this...

We start with
$$\int_{- \infty}^{\infty}{e^{-x^2}} dx = \sqrt{\pi}$$

We consider
$$\int_{- \infty}^{\infty}{e^{-tx^2}} dx = \int_{- \infty}^{\infty}{e^{-u^2}} \frac{d(t^{-0.5}u)}{du}du = \int_{- \infty}^{\infty}{e^{-u^2}} t^{-0.5} du = t^{-0.5} \sqrt{\pi}$$

This leads to
$$\frac{d}{dt} \int_{- \infty}^{\infty}{e^{-tx^2}} dx = \frac{d}{dt} t^{-0.5} \sqrt{\pi} = \frac{-\sqrt{\pi}}{2} t^{-\frac{3}{2}}$$

 

[StatusX]

Here's a problem:

You find yourself in the middle of a forest, with no idea how you got there. You find a note on a nearby tree that says the edge of the forest is 1 mile away. Of course, you have no idea what direction it's in. Assuming you know the forest is a half-plane (ie, from above, it looks like the set of points {(x,y) | y>0}), what path should you take to minimize the distance you need to travel to find the edge?

(Specifically, what path minimizes the distance traveled in the worst case scenario. It might also be interesting to find the path that minimizes the expected distance, although this sounds harder).

Hint:

Spoiler

You can do better than the obvious path of length 2pi + 1.

 

[chingkui]

Go 1 mile in any direction, and then go along the circle with 1 mile radius about the origin for 270 degrees, then instead of walking along the remaining 90 degrees of the circle, depart from the circle and walk 1 mile along the tangent of it. Not sure if this is optimal in worst case, but certainly is the best I can come up so far.
Haven't try to solve the expected distance version though.

 

[StatusX]

You can do slightly better than that. Go in a straight line for sqrt(2) miles in, let's say, the northwest direction, then travel south to the west edge of the 1 mile radius circle surrounding your starting point, walk along the southern half of the circle, and then go a mile north, so that you finish sqrt(2) miles northeast of where you started.

I haven't been able to prove this is optimal yet, or tried to work out the expected distance version, so those are still things someone could try.

 

[qntty]

I will have a guess and I think it goes something like this...

We start with
$$\int_{- \infty}^{\infty}{e^{-x^2}} dx = \sqrt{\pi}$$

We consider
$$\int_{- \infty}^{\infty}{e^{-tx^2}} dx = \int_{- \infty}^{\infty}{e^{-u^2}} \frac{d(t^{-0.5}u)}{du}du = \int_{- \infty}^{\infty}{e^{-u^2}} t^{-0.5} du = t^{-0.5} \sqrt{\pi}$$

This leads to
$$\frac{d}{dt} \int_{- \infty}^{\infty}{e^{-tx^2}} dx = \frac{d}{dt} t^{-0.5} \sqrt{\pi} = \frac{-\sqrt{\pi}}{2} t^{-\frac{3}{2}}$$

This is correct.
There is another way to do this with dimensional analysis which I found in some MIT lecture notes. Say that x have some dimension D. The exponent needs to be dimensionless to make sense, so t must have the dimension $$1/D^2$$. And dx has the same dimension as x, so the result which contains t must have dimension D. $$1/\sqrt{t}$$ has dimension D, so we can say that

$$\int_{- \infty}^{\infty}{e^{-tx^2}} dx = \sqrt{\frac{\pi}{t}}$$

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

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

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

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

Recall that $$e^t e^{-x^2} = e^{-x^2+t} \not= e^{-tx^2}$$

 

[Georgepowell]

Here is a good question if someone wants a go:

A space-ship of (constant) mass M starts from rest in a zero gravity vacuum. It has a rocket that provides a constant force of F Newtons in any direction it wants. The space-ship's aim is to travel in a perfect circle of radius R from rest by using its rocket.

Find the direction (angle, theta) that the rocket should fire in terms of T for time, R, M, and F.

 

[Awsom Guy]

Mathemagician

 

[maze]

Here's a problem:

You find yourself in the middle of a forest, with no idea how you got there. You find a note on a nearby tree that says the edge of the forest is 1 mile away. Of course, you have no idea what direction it's in. Assuming you know the forest is a half-plane (ie, from above, it looks like the set of points {(x,y) | y>0}), what path should you take to minimize the distance you need to travel to find the edge?

(Specifically, what path minimizes the distance traveled in the worst case scenario. It might also be interesting to find the path that minimizes the expected distance, although this sounds harder).

Hint:

Spoiler

You can do better than the obvious path of length 2pi + 1.

edit: nm

 

[Awsom Guy]

The answer is 1 mile. Because you are in the middle so going out can be anywhere so it is 1 mile from the middle.

 

[Awsom Guy]

edit: nm

The answer is 1 mile. Because you are in the middle so 1 mile to the end.