LaTeX
algorithm
inequalities
combinatorics unsolved
combinatorics

Provided $k \geq 3$ equally looking coins, one of the coins has a weight distinct from all other coins (the other coins have equal weight). In n tests with the well-known balancing scale one shall determine which is the coin with the distinct weight and whether this coin is lighter or heavier than the others. Determine dependently on n the greatest number of coins that can be tested.

I guess we need to prove that $3^{n-1}$ is the greatest possible number of coins to test.

If I remember correctly your are right.  :)

[quote="Myth"]Obviously, we can test $3^{n-1}$ coins.[/quote]

isn't that when we know if the other coin is heavier or lighter than the others?in this case it seems we have to figure that part too.
i remember that there was some similar qn with 3 weighings and 12 coins.

Yes, we can find false coin within 12 coins with 3 weightings if we know heavier or lighter this false coin.

i can find the false coin in 12 coins by 3 weightings [b]without[/b] knowing the false coin is heavier of lighter than the others
So that .. the answer : 3^{n-1} may be not right ...

[quote="InToTheRainBow"]i can find the false coin in 12 coins by 3 weightings [b]without[/b] knowing the false coin is heavier of lighter than the others.[/quote]
Ok! Show it!

it was not too hard ,myth .. i think u can try it ...
[hide]first , u get 3 groups a1,a2,a3,a4(group A) - b1,b2,b3,b4(group B )- c1,c2,c3,c4 (group C )

Get 2 A and B weighting
[b]1) if they are equal [/b]

==> the false coin is in group C
get 3 coins in group A and 3 coins in group C , we will get the answer

[b]2 ) if they are not equal[/b]

=>left: A (a1,a2,a3,a4) <right: B (b1,b2,b3,b4) ( if A > B ... it is the same - ofcourse )
we move a1,a2,a3 to the right , move b1,b2,b3 out
and move c1,c2,c3 to the left
 .   if left < right  ==> the false coin is a4
 .   if left = right  ==> the false coin is in (b1,b2,b3 ) and it is heavier (because at first ,A <B ) ==> we get the answer after 1 more weighting
 .   if left > right  ==> the false coin is in (a1,a2,a3 ) and it is lighter ==> we get the answer too .

---
my english is not good  , sorry ...
by the way .. can i know how old you are ?[/hide]

[quote]Provided k \geq 3 equally looking coins, one of the coins has a weight distinct from all other coins (the other coins have equal weight). In n tests with the well-known balancing scale one shall determine which is the coin with the distinct weight and whether this coin is lighter or heavier than the others. Determine dependently on n the greatest number of coins that can be tested.[/quote]
With n = 3 k , i can prove that we can weight 12x3^{k-1} coins

But $12\cdot 3^{k-1}$ is much lesser then $3^{3k-1}=3^{n-1}$. Maybe you meant something else?

sorry ... i was wrong in typing .
it is n = 3+k not 3k

so .. 12 x 3^ (k+1) > 3^(k+2)
ok ?

i guess that :
if n >= 3 ==> n = 3 +k (k >=0 )==> the maximum number of coins is 12 x 3^(k-1)
but it is a problem for n = 2 . if there are 2 coins , we can not find the false coin , if there are 3 ,we can find ...
and for n = 1 , we can not find it (unless the number of coins is 1 )

BTW ... what is " k \geq 3" ?

It was Latex notation for $\geq$. I have corrected it.

I read a paper ( just at elementary level, dont worry :D  ), there is a proof of the fact that with $n$ weightings, we can determine the false coin among
$(3^n-3)/2$ coins. This, by the way, satisfies the couple $12,3$ one mentioned above ;) . The solution is really elegant, worth enjoying!! I'm on my exam now, but when I am less busy, I will surely post it here for you guys :lol:
 Now, try to prove that the best number must be less than or equal to $(3^n-1)/2$

Ok! I can prove it!
Suppose we are able to test $m$ coins.
Each weighting have one of three results: $<$, $=$ or $>$. So after $n$ weighing we will have $3^n$ different sequences of weighing results. Each of these sequences must recognize false coin, but false coin can be one of $m$ coins and it can be ligher or heavier, i.e. $3^n$ sequences must be able to recognize $2m$ distinct cases. It follows that $3^n\geq 2m$, so $m\leq \frac{3^n-1}{2}$.
Final step: we can apply InToTheRainBow's strategy to determine false coin within $\frac{3^n-1}{2}$ coins.
[b]Note[/b] that InToTheRainBow prooved that he can recognize false coin within 12 coins using 3 weighing, but we need strategy for recognizing false coin within 13 coins using 3 weighings.
Is it possible to impove your strategy, InToTheRainBow?

In my last post, I said somthing incorrect. :blush:
 Using $n$ weighings we can indentify the false coin among $(3^n-3)/2$
 And $n$ is the necessary number for $(3^n-3)/2$ coins.
 Yet my paper doesn't mention about the maximum number of coins. Infact, Myth's proof provide a very good upper bound : $(3^n-1)/2$

-_-
k =(3^n -1)/2 ...
n =3 ==>k =14
can u find the false coin among 14 coins ?
(may be i will try ... i must go now ... )

I think we can recognize false coin within 13 coins for 3 weighings.
InToTheRainBow should check it ;)

my fd had an very interesting way to do it.

(1)
If you just want to identify the fake coin without knowing whether it is heavier or lighter than normal ones, you need to weigh 3 times.
1st time: Left: (No. 12,10,6,5) Right: (No. 11,9,8,7)
---if Left>Right, get 9 points
---if left<right, get -9 points
2nd time: left: (No. 12,7,3,2) Right: (No. 11,6,5,4)
---if left>right,get 3 points
---if left<right,get -3 points
3rd time: left: (No. 11,10,8,1) right: (No. 7,5,4,2)
---if left>right,get 1 points
---if left<right,get -1 points

A = total number of points
if A=0 then No.13 is the fake one.
if A>0 then No.A is the fake one.

(2) If you have to know whether the fake coin is heavier or lighter htan the normal coin, you can use the same method in (1), but you have to put no.13 on the left hand side and a real coin in the right hand side each time.

A=total no. of points
No. |A| is the fake coin.
If A>0, the fake coin is heavier.
If A<0, the fake coin is lighter.

I can :D . It is very similar to the method I read on the paper. But again, the result is $3,12$ ( $( 3^n-3 ) /2 $ ) :P . Siuhochung's method is $13$
Hm...

I think I also have a method for 13 coins.

I don't doubt that!! ;)
 I believe the method of Siuhochung is correct.
 Reason : his method has something to do with 3-base ( see the points,  )  The method for the general case labels all the coins in 3-base
 And the way Siuhochung draw conclusion is exactly the same

u didn't doubt that we can find the false coin in 13 coins ?
Ofcourse we can find .
It is really the same as when we find the false coin in 12 coins .
Try it ,man .
n=3 ===> the maximun coins is 13 .

can someone  find the correct fomular for it ?

What is the problem? I proved that we can't recognize more than $\frac{3^n-1}{2}$ coins. And we constructed (?) method for recognizing exactly $\frac{3^n-1}{2}$ coins. So we are done.

[quote="dickchimney"]To TotheRainbow: I have edited my post. It is $(3^n-3)/2$ now. But look at your post (and Myth's )!! It seems that it is not me the only one having trouble with basic calculation, huh? :D[/quote]
i think $(3^n-3)/2$  is not right .
if n = 2 . i can find the false coin in 4 coins.
but $(3^2-3)/2$ = 3 .

:what?: Have you read my previous reply? No one prove that $\frac{3^n-3}{2}$ is correct answer. We just need slighly improve your algorithm for general case to force him to recognize $\frac{3^n-1}{2}$ coins.

Felix's mom asked him to find the fake coin among 12, and labeled them with letters, showing he could solve the problem (not licked yet!):

F AM NOT LICKED

and then weighed

MA DO against LIKE
ME TO against FIND
FAKE  against COIN

and then knew which one was the heavy/light one, and whether it was heavy or light!

Source: John Conway in a post at
http://groups-beta.google.com/group/geometry.puzzles/browse_thread/thread/2beb3edf8f39acde/

Since there are SO many places where I see this problem, I get the feeling that 12 coins is the most.  And I'm pretty convinced 13 is impossible with 3 weighings; in fact, I have a proof, but this box is too small to contain it :)

--Joshua Zucker

[quote="siuhochung"]
(2) If you have to know whether the fake coin is heavier or lighter htan the normal coin, you can use the same method in (1), but you have to put no.13 on the left hand side and a real coin in the right hand side each time.

A=total no. of points
No. |A| is the fake coin.
If A>0, the fake coin is heavier.
If A<0, the fake coin is lighter.[/quote]

And you DO have to know whether the fake coin is heavier or lighter, if you go by the posting that started this whole thread, it gives that restriction.

And I have some trouble with "put no 13 on the left and a real coin in the right" -- if we had coin #14, which was known to be real, along with 1-13 one of which is counterfeit, OK, I can do that.

Otherwise how do I put a real coin in the right?  I don't know which coin is real!

--Joshua Zucker

[quote="Joshua Zucker"] And I have some trouble with "put no 13 on the left and a real coin in the right" -- if we had coin #14, which was known to be real, along with 1-13 one of which is counterfeit, OK, I can do that.

Otherwise how do I put a real coin in the right? I don't know which coin is real![/quote]

The coin-weighing problem is an old classic (Joshua Zucker provided a link to a John Conway quote, which says it dates from the 1940's). It has spawned some variants. They are:

1. We have m coins with one of unequal weight, a balance scale, and nothing else. Find that unequal coin and whether it is heavier or lighter than the others in n weighings. In that case $m=\frac{3^n-3}{2}$.

2. Same as version 1, except that we also have extra coins that are known to match the weight of the equal-weight coins (siuhochung called these "real coins"). $m=\frac{3^n-1}{2}$.

3. Same as version 1, except the question is only to find the unequal coin. We don't care whether it is heavier or lighter. $m=\frac{3^n-1}{2}$.

4. I haven't seen this variant before, but we could combine the changes for versions 2 and 3. We have some coins of known weight and we don't care whether the unequal coin is heavier or lighter. $m=\frac{3^n+1}{2}$.

Myth has analyzed version 2 and thus gotten the result that $m=\frac{3^n-1}{2}$. This is the simplest version to analyze.

After the first weighing, version 1 acts like version 2, because the first weighing identifies some equal-weight coins. However, that first weighing in version 1 has to involve an equal number of coins of unknown quality on each side of the scale, which leads to some inefficiency. Let me repeat Myth's analysis to show the complication.

Each weighing has three possible results: left heavier than right, left equal weight to right, and left lighter than right. So if we conduct n weighings, we have $3^n$ possible outcomes. If we have m coins, we have 2m possible cases (m choices of the unequal coin and 2 choices whether it is heavier or lighter). So $2m\leq 3^n$. This means an upper bound on 2m is $3^n-1$, because $3^n$ is odd.

Our first weighing has k coins on each side of the scale. Our outcomes are:
Left heavier: Either the k coins from the left side contain a heavy coin or that the k coins on the right contain a light coin. That is 2k cases. (Furthermore, all the coins off the scale are equal-weight coins.)
Left equal: The unequal coin is in the m-2k unweighed coins. We have no clue whether it is heavy or light. That is 2(m-2k) = 2m-4k cases. (Furthermore, all the coins on the scale are equal-weight coins.)
Left lighter: Either the k coins from the left side contain a light coin or that the k coins on the right contain a heavy coin. That is 2k cases. (Furthermore, all the coins off the scale are equal-weight coins.)

We can test only $3^{n-1}$ outcomes in the remaining n-1 weighings, so we have $2k\leq 3^{n-1}$ and $2m-4k\leq 3^{n-1}$. Since $3^{n-1}$ is odd, that really gives $2k\leq 3^{n-1}-1$ and $2m-4k\leq 3^{n-1}-1$. Summing twice the first inequality and the second inequality gives $2m\leq 3^n - 3$. Our best result is that $m=\frac{3^n-3}{2}$ and in the first weighing $k=\frac{3^{n-1}-1}{2}$.

In version 2, where we start with extra known equal-weight coins and $m=\frac{3^n-1}{2}$, we can divide our cases in the first weighing more efficiently. The first weighing has $k=\frac{3^{n-1}+1}{2}$ coins on each side (one more coin than the first weighing in version 1). All the coins on the left are unknown coins. k-1 of the coins on the right are known coins, but the kth coin is a known equal-weight coins from our extra supply.

Our outcomes from that weighing are:
Left heavier: Either the k unknown coins from the left side contain a heavy coin or that the k-1 unknown coins on the right contain a light coin. That is $2k-1 = 3^{n-1}$ cases.
Left equal: The unequal coin is in the m-(2k-1) = m-2k+1 unweighed coins. We have no clue whether it is heavy or light. That is $2(m-2k+1) = 3^{n-1}-1$ cases.
Left lighter: Either the k unknown coins from the left side contain a light coin or that the k-1 unknown coins on the right contain a heavy coin. That is $2k-1 = 3^{n-1}$ cases.

We can actually leave an odd number of cases, exactly $3^{n-1}$, after the first weighing if we work with known equal-weight coins. That gives greater efficiency for that first weighing than we had with version 1.

For versions 3 and 4, we don't care about the unequal coin's weight. Optimists might assume that, therefore, we have only m cases, not 2m cases. Alas, when we are done, we are probably going to know whether the coin is lighter or heavier anyway, still doubling that case. Only when we avoid weighing that coin can we avoid splitting the case. So we need a scheme in which sometimes the unequal coin is never weighed. However, if the unequal coin is among the unweighed coins, then the weighed coins are all proven to be of equal weight. So we would keep weighing roughly 2/3 of the unweighed coins until finally after n weighings we had one last coin that was never weighed, which by elimination would be the unequal coin. Because of this, our weighing scheme for version 3 may simply be the weighing scheme for version 1 with an extra unknown coin off to the side, and our weighing scheme for version 4 may simply be the weighing scheme for version 2 with an extra unknown coin off to the side. That lets us judge one more coin, not twice as many coins.

Erin Schram


Prove that system equation
             $ x^2 \plus{} y^2 \equal{} zw$ and $ z^2 \minus{} w^2 \equal{} 2xy$
no solution in $ N^*$

My solution is very long and complicated (if I write it may be 3.5 to 4 page   :( )
I hope to see solution nice,short in this topic

I need a help from anyone.
Ps.I think that here is a result famous but I can't find it.


Wow.. I really get lazy with "regularly" visiting this forum  :D

Thanks to Ralph, I'm here once again, and I thought.. since so many of us Seminar people will be at Waterloo next year, maybe we can have a Seminar get-together thing sometime before frosh week?

Anyone interested?

Jenn!!  Yea, we miss you a lot on the forum!  Post more!

YES!  We definitely need to have a get-together sometime.  Everybody flying in from outta town, WHEN DO YOU GET HERE??!?!

Is this going to be a seminar only thing, or a canadian mathlinks thing  :D ? Some of us also want invites, reguardless of our ability to get to the seminar  :blush:

43 days!!!!!!!!!!!

Flying in September 3rd.  Um, that's when they told me to move in, and I'm not allowed to move in sooner.

Ooooh yeah we so should have like seminar "reunions", it would be so much fun, anyone could come, but they'd have to live with playing seminar games (mao, mafia, 24) etc. and David Rhee trying to kill them first round first game etc. :D

Except the DDR machine is out!!!  Which makes SLC a lot crappier :'(  Although I'm sure Elyot and I could bring our DDR pads..

There is discussion about a seminar reunion here:
[url]http://groups.msn.com/UWmathseminar06/general.msnw?action=get_message&ID_Message=12&ShowDelete=0&ID_CLast=27&CDir=-1[/url]
[url]http://groups.msn.com/UWmathseminar06/general.msnw?action=get_message&mview=0&ID_Message=12&LastModified=4675581746335190918[/url]

[quote="Elyot"]DDR Machine will hopefully be back in the fall... apparently they only get rid of it for summer term because waterloo's population goes down by like 50-60%[/quote]

Yay!!!  That's good news   :D

[size=100]So.. when are you guys available to have the "reunion" thingy??

Post time, and we should try to work it out..
I'm thinking either Sept 3rd (I might not be here though) or on Thursday during orientation week. We have free time before the dance, so that should work out too..

What do you guys think?

And.. what do you want to do? Dinner? Seminar games? [/size]
[size=34]Bugging ian?[/size]

It could be like, a mass seminar mathlinks reunion!!  For seminar people of all years, lol.  (Cuz i wanna go play ddr!  [size=59]and bug IAN of course!!!![/size])

Hehehe looking forward to seeing ppl again!!

[size=34]I say we should go in the seminar t-shirts. THat should look more intimidating!![/size]

The "Invertibles" T shirt is cool.
[size=9]a babe magnet!  yarr lollerskates[/size]

[quote="Singular"]

[size=9]a babe magnet!  yarr lollerskates[/size][/quote]

WTF?!?!  LOL.  Don't make me melt your face with my lollerblaster.

my ROFLCOPTER pwns your lollerblaster!!!

hehe

I'll be on co-op during the fall, so we'll have to plan something for an evening or weekend.  That said, I will probably be showing up a few times each week for clubs, events, putnam training, etc... so I'll be around and we'll be able to plan lots of times to get together!

Also, I say we should find some time one weekend or another to take a trip down to Kitchener, where, of course, we can go to Zappers Arcade and play on their IN THE GROOVE machine, which is like a souped-up version of DDR with crazier music and way way harder steps.  There are 13-foot songs on that thing, which have MINES (which EXPLODE if you have your foot on the button when they pass by) and HANDS (jumps and holds with more than 2 arrows at a time!)  It's rediculously fun, and well worth the trip down to kitchener (which is cheap and easy by bus).  And of course, we can visit all of the random fun places in K-town.

Of course, it's also good to get off campus sometimes.  A disturbing number of first years living in residence NEVER LEAVE CAMPUS.  EVER.  And this is not good, cuz Kitchener and Waterloo are nice cities with tons of fun stuff to do.  Anyone like lazerquest?!?!

I still don't understand your infatuation with bugging Ian.  LOL.

In the groove?? Sounds insanely hard! I definitely want to try though! Argh, that's going to be a lot of money to be wasted though, considering that I'll probably not clear the 1st round!  :D

[quote]In the groove sounds ridiculous.[/quote]

What's with you two??  :D

[quote]I still don't understand your infatuation with bugging Ian. LOL.[/quote]

oooooh Sarah, you should scan/post that picture!! That's like the only evidence we have, I think!

[quote="jpark"]
oooooh Sarah, you should scan/post that picture!! That's like the only evidence we have, I think![/quote]

*sniff*  That picture.....*sniff*.  That hurt.  Cut real deep. lol I'll bring it to waterloo as proof!

Good question though.  How'd this whole thing start? lol!

Laserquest is FUN.  THough I'm awful and miserable at it, I like to play. Hahahaha oh yeah...I'm definitely really really bad at that game!

I have to say, that picture really was horrible! The "feud" has been going on for too long though, so that we both forget why it started, lol. I wonder if Ian remembers. Maybe we should call a truce of some sort.

Can't say I've ever played laserquest, but I'm willing to try!!  :D

[quote="Elyot"]Actually... I just went by Zappers today; apparently they're closed for renovations, but hopefully we'll be able to go in the fall when it opens up.  Maybe Waterloo will get an IN THE GROOVE machine sometime.  And don't worry Jenn... there are still easy songs on it.

And you seriously haven't been to laserquest, despite living in K/W, even though Sarah has, when she lives in the middle of nowhere?  WTF?!?!  :P[/quote]

LOL!! lasequest down at king street is awesome lol

[quote="Elyot"]Actually... I just went by Zappers today; apparently they're closed for renovations, but hopefully we'll be able to go in the fall when it opens up.  Maybe Waterloo will get an IN THE GROOVE machine sometime.  And don't worry Jenn... there are still easy songs on it.

And you seriously haven't been to laserquest, despite living in K/W, even though Sarah has, when she lives in the middle of nowhere?  WTF?!?!  :P[/quote]

Hmm.. I played something that resembled DDR when I went to Bingeman's at the Seminar. I wonder if that's in the groove. It did have weird stuff that you weren't supposed to step on etc..

And yup, definitely haven't been to laserquest! FYI, I live in the middle of nowhere as well! My part of the town (by the Laurel Creek) has NOTHING! And I don't drive, so I can't go to many places! (It has one city bus, which stops running at 9pm, and the bus stop is about 5-10 minutes walk from my house as well)

LOL, we don't even have a bus here   :D
It's like a 20 min bike ride to the other side of town, lol.

I don't drive either... I'd die if it weren't for the bus and my bike!  But I'm fortunate enough to live close enough to fairview mall that I can catch a ton of different buses when needed.  The #8 drops me like 3 mins from home, but it's 10-15 min walk to the mall to catch a 12, 7, or express.

*sniff*
I'm a WHOLE 30 mins by car from the closest mall!!!  *sigh*  lol Definitely not a bike-rideable trip...unless I feel like riding on the highway...

I guess you win Sarah, somehow I feel like I should feel thankful for having a bus..  :D Although, it's hard for me to get to a mall too.. The nearest mall (Conestoga mall) would take about 30mins-1hour by bus, because the bus in my part of the town (#13) doesn't go anywhere other than the UW, so I have to get to the UW first (which is the opposite direction from the mall) and take the Express from there!

Definitely need to learn to drive soon!!  :D

Yes we could bike, there are some very nice bike trails through forests here.  I'm gonna go to driving school as soon as I get back from China.

hahaha Yeah at Bingemans they had this DDR machine with the 4 corner and centre as buttons, and UDLR as nothing.  Jenn owned me at it.

Mines suck, I honestly think they ruin the elegance of the game.  Maybe it's cuz I keep stepping on them; you can make them in SM.

Hmm I miss seminar games, I think we should certainly play some either before or during Frosh week..the times Jenn suggested sound good.

PS Where can I buy set cards?  :D


search probability function calculus derivative topology

I saw this being used as a lemma on scribd without proof:

"If $ O \subset \mathbb{R}^{2}$ is an open disk and $ f: O \rightarrow \mathbb{R}$ is differentiable with $ \frac{\partial f(x,y)}{\partial y} \equal{} 0, \forall (x,y) \in O$, then $ f$ is independent of $ y$"

What does it mean for $ f(x,y)$ to be independent of $ y$, because every search I make for independence usually ends up with me reading an article on the notion of independence in probability?

It means $ f(x, y_1) \equal{} f(x, y_2)$, i.e., $ f$ is a constant function with respect to $ y$.  The value of $ f$ is independent of (does not depend on) the value of $ y$.

Would you use some kind of generalized MVT to prove it?

Not a generalization at all. This is a one-dimensional problem.

OH, right, you could just take $ \phi(y) \equal{} f(x,y)$ and apply one-dim MVT...

But what if the open set was only connected, but not path-connected. Would this affect the truth of the lemma? For example, I can see how connectedness is so important in order for a partial derivative to exist, but is it enough to still claim that $ f(x, y_{1}) \equal{} f(x, y_{2})$?

Connectedness has nothing to do with the existence of derivatives, and everything to do with whether we can turn a zero derivative into constancy.
Of course, you're looking at the wrong sort of connectedness here; connectedness in $ \mathbb{R}^2$ doesn't help at all. This statement is true on a union of two disjoint disks $ (x \minus{} 2)^2 \plus{} y^2 < 1$ and $ (x \plus{} 2)^2 \plus{} y^2 < 1$, and the statement is false on a "pac-man" shaped region $ x^2 \plus{} y^2 < 1, x \minus{} |y| < 0$. It's all about whether the vertical slices are connected.

why is it that connectedness in $ \mathbb{R}^2$ wouldn't help? Would it not help on any higher-dim $ n$ as well?

Reread jmerry's post and draw the examples jmerry suggested and think about it for more than 3 minutes  :roll:


Prove that  the toitent of rs=g * the toitent of r * the toitent of s/the toitent of g

Let g = gcd(r,s)

$
tot(rs) = rs \prod_{p|rs}1-1/p
\\
tot(r) = r\prod_{p|r}1-1/p = r(\prod_{p|r\ not\ s}1-1/p)(\prod_{p|g}1-1/p)
\\
tot(s) = s\prod_{p|s}1-1/p = s(\prod_{p|s\ not\ r}1-1/p)(\prod_{p|g}1-1/p)
\\
tot(g) = g\prod_{p|g}1-1/p
\\
\\
g\displaystyle{\frac{tot(r)tot(s)}{tot(g)}=\frac{grs(\prod_{p|r\ not\ s}1-1/p)(\prod_{p|g}1-1/p)s(\prod_{p|s\ not\ r}1-1/p)(\prod_{p|g}1-1/p)}{g\prod_{p|g}1-1/p}}
\\
\\
=rs(\prod_{p|r\ not\ s}1-1/p)(\prod_{p|s\ not\ r}1-1/p)(\prod_{p|g}1-1/p)
\\
=rs(\prod_{p|rs}1-1/p) = tot(rs)
$

Sorry for the poor readability.

The number of positive integers less than n that are relatively prime to n:
[url]http://mathworld.wolfram.com/TotientFunction.html[/url]


superior algebra
superior algebra unsolved

Let $ \rho : G \to GL(V)$ be an irreducible representation and let $ \chi_{\rho}$ be its character. Suppose that $ x \in G$ is of order 2. Show that $ \chi_{\rho} (x)$ is an integer and that $ dim(V)\minus{}\chi_{\rho}(x)$ is even.

the group of order 2 has two irreducible representations, the trivial one and the sign homomorphism. Let's call the first character $ \chi_1$ and the second one $ \chi_2$.
Then there exists nonnegative integers $ m_1$, $ m_2$, so that $ \chi_{\rho} \equal{} m_1 \chi_1 \plus{} m_2 \chi_2$ (on $ < x >$). Then of course $ \chi_{\rho}$ is an integer. Now, put 1, we have $ dim(V) \equal{} m_1 \plus{} m_2$, put $ x$ we have $ \chi_{\rho}(x) \equal{} m_1 \minus{} m_2$. Subtract these two we have the desired conclusion.


Let $ a,b,c,d > 0$,provt that:

$ \frac {a^2}{b(b \plus{} c)} \plus{} \frac {b^2}{c(c \plus{} d)} \plus{} \frac {c^2}{d(d \plus{} a)} \plus{} \frac {d^2}{a(a \plus{} b)} \geq \frac {2}{3} \plus{} \frac {a^2}{b(b \plus{} c \plus{} d)}$
$ \plus{} \frac {b^2}{c(c \plus{} d \plus{} a)} \plus{} \frac {c^2}{d(d \plus{} a \plus{} b)} \plus{} \frac {d^2}{a(a \plus{} b \plus{} c)}\geq 2.$

$ {\frac {{a}^{2}b}{\left( b \plus{} c \right) cd}} \plus{} {\frac {{b}^{2}c}{\left( d \plus{} c \right) da}} \plus{} {\frac {{c}^{2}d}{\left( a \plus{} d \right) ab}} \plus{} {\frac {{d}^{2}a}{\left( b \plus{} a \right) bc}} \geq 2.$


Prove that the equation:
$ x^2 \plus{} y^2 \plus{}z^2 \equal{} (x\minus{}y)(y\minus{}z)(z\minus{}x)$

has infinitely many solutions for $ x,y,z \in \mathbb{Z}$

For example $ z\equal{}k, x\equal{}\frac{k\minus{}k^2\minus{}1}{2k\minus{}1}, y\equal{}k\minus{}1$

[quote="Ahiles"]For example $ x \equal{} \frac {k \minus{} k^2 \minus{} 1}{2k \minus{} 1}$[/quote]

Does not look like an integer :wink:

Pierre.

[color=darkblue]But there are infinetely many integer numbers of this form...

Let $ \frac {k \minus{} k^2 \minus{} 1}{2k \minus{} 1} \equal{} p$.

Then $ k_1 \equal{} \frac {1}{2}(1 \minus{} 2p \minus{} \sqrt {4p^2 \minus{} 3})$
        $ k_2 \equal{} \frac {1}{2}(1 \minus{} 2p \plus{} \sqrt {4p^2 \minus{} 3})$
But we know that there are infinetely many perfect squares of the form $ 4p^2 \minus{} 3$[/color]

[quote="Ahiles"][color=darkblue]
But we know that there are infinetely many perfect squares of the form $ 4p^2 \minus{} 3$[/color][/quote]
In fact, there are finitely many integers $ p$,such $ 4p^2 \minus{} 3 \equal{} n^2$,because this equation implies that
$ (2p \minus{} n)(2p \plus{} n) \equal{} 3$,but this equation has unique solution $ (1,1)$.

for $ |k| > 2$, if $ 2k \minus{} 1|k^2 \minus{} k \plus{} 1\implies 2k \minus{} 1|k^2 \minus{} k \plus{} 1 \plus{} (2k \minus{} 1)$
$ \implies 2k \minus{} 1|k(k \plus{} 1)\implies 2k \minus{} 1|k \plus{} 1\implies 2k \minus{} 1|2k \plus{} 2$
$ \implies 2k \minus{} 1|2k \plus{} 2 \minus{} (2k \minus{} 1)\implies 2k \minus{} 1|3$ an impossibility.
Let me make it a bit simpler
$ x \equal{} (2k \minus{} 1)(6k^2 \plus{} 1),y \equal{} 2k(6k^2 \plus{} 1),z \equal{} (2k \plus{} 1)(6k^2 \plus{} 1)$

[quote="Carlez Tevos"][quote="Akashnil"]for $ |k| > 2$, if $ 2k \minus{} 1|k^2 \minus{} k \plus{} 1\implies 2k \minus{} 1|k^2 \minus{} k \plus{} 1 \plus{} (2k \minus{} 1)$
$ \implies 2k \minus{} 1|k(k \plus{} 1)\implies 2k \minus{} 1|k \plus{} 1\implies 2k \minus{} 1|2k \plus{} 2$
$ \implies 2k \minus{} 1|2k \plus{} 2 \minus{} (2k \minus{} 1)\implies 2k \minus{} 1|3$ an impossibility.
[/quote]

How is this related to the solution  :maybe:[/quote]It is related to Ahiles' solution, which is apparently wrong.

Thanks for your explanation, Johan. I thought it was related to Akashnil's solution  :)

And, Akashnil, can you please explain how you got your solution?  :lol:

[quote="Carlez Tevos"]How is this related to the solution  :maybe: [/quote]
This is not related to my solution, as Johan said.
[quote="Carlez Tevos"]And, Akashnil, can you please explain how you got your solution?  :lol:[/quote]
For some $ x,y,z$ if we multiply a constant $ c$ to all of them, then LHS gets multiplied by $ c^2$ while the RHS by $ c^3$. So I wanted to show that there exists infinitely many $ x,y,z$ for which $ (x\minus{}y)(y\minus{}z)(z\minus{}x)|x^2\plus{}y^2\plus{}z^2$. So my first idea was to make RHS very small, like $ 1,2$. So I took 3 consecutive numbers for the initial $ x,y,z$. Then RHS=2. But the LHS had to be even. Thus I took $ (x_0,y_0,z_0)\equal{}((2k\minus{}1),2k,(2k\plus{}1))$  And then took the suitable $ c$ to be $ \frac{LHS}{RHS}$ which is $ (6k^2\plus{}1)$

Also u might take a look at http://www.mathlinks.ro/viewtopic.php?t=212364
The Idea is similar there.


Billy is attending "Moore Academy", an all-boys school on a river that is consistently 3 km wide and straight. He would like to ask one of the students of "Edgar Prep School for Girls" to go out this weekend, but he must hurry since this particular girl is being courted by many other boys. Edgar School is located 8 km downriver from Moore Academy, but on the other side of the river. Billy can row 6 km/hr and run at 8 km/hr. How far down the river should he row in order to reach Edgar school in a manner that minimizes the time he takes to get there.

is the answer 3.4?

thanks

This problem is very similar to Snell's law, which explains the breaking of light when it goes from one medium to another.

First some notation: $ l=8 \text{km}, w = 3 \text{km}, v_1 = 6 \text{km\h}, v_2 = 8 \text{km\h}$. And let $ x$ be the distance Billy rows down the river. Then the distance traveled by boot is: $ \sqrt{w^2 +x^2}$ while the running distance is: $ l-x$. To time for the total trip is therefore:$ t = (l-x)/v_1 + \sqrt{w^2 +x^2}/v_2$. To find the minimum time, we differentiate $ t$ with respect to $ x$ and put it to zero:  \[ \frac{-1}{v_1} + \frac{x}{v_2 \sqrt{w^2 + x^2}} =0\] Solving for $ x$ gives:$ x=9\sqrt{7} \approx 3.4 \text{km}$


algebra
polynomial
topology
algebra proposed

[b]Formulation 1. [/b] Let $\beta$ be a nonzero complex number. Show that there exists a constant $c(\beta) > 0$ with the following property: every monic integer polynomial not of the form $(z-m)^{d}, m \in \mathbb{Z}$ has a zero outside of the disk $|z-\beta| < c(\beta)$.

[b] Formulation 2. [/b] Let $\beta \in \mathbb{C}$. Show that there exists a constant $c(\beta) > 0$ with the following property: for any $z_{1},\ldots,z_{d}$ in the disk $|z-\beta| < c(\beta)$, not all equal, there is some $1 \leq s \leq d$ with $\sum_{i_{1}< \cdots < i_{s}}z_{i_{1}}\cdots z_{i_{s}}\notin \mathbb{Z}$.

Choose a formulation, and kill the problem!  :P

(Question -- to what extent does $c(\beta)$ really depend on $\beta$?...)

I just realized that the answer to this question is completely trivial... There is an absolute such $c$... At least, we could try to find the largest such constant :blush:

Here is a more meaningful quesion (hopefully...)

Call a measurable subset $M \subset \mathbb{C}$ [i]algebraic[/i] if there exist infinitely many algebraic integers $\alpha \in M$ such that all of their algebraic conjugates also belong to $M$. In other words, we call $M$ "algebraic" if there are infinitely many *monic* integer irreducible polynomials all of whose zeros belong to $M$.

For examples: the unit disk $|z| < 1$ is [b]not[/b] algebraic, but the closed disk $|z| \leq 1$ is; the real line $\mathbb{R}$ is algebraic, but no finite segement of it is.

Which sets are algebraic? What do you know (anything!) about "algebraic sets"? What can you show/conjecture about them?

Let me try first. Here's what I [think I can] show:

1. Certainly, I can show that for every finite set $S$ (of points), there exists an open set (open neighborhood) $A \supset S$ which is NOT algebraic.

2. But I think we can claim more: for every $n$, there is a constant $r_{n}>0$ such that for any set $S$ of $n$ points in the plane, the set $\cup_{a \in S}B_{r_{n}}(a)$ is NOT algebraic. In other words: there is an $r_{1}> 0$ such that no circle of radius $r_{1}$ is algebraic; there is an $r_{2}> 0$ such that no union of two circles of radii $r_{2}$ is algebraic; and so on.

3. For every $\varepsilon > 0$, the annulus $1 < |z| < 1+\varepsilon$ is algebraic.

4. In fact, every annulus of inner radius $\geq 1$ is algebraic. (but this I don't know how to show)


There are $ n$ married couples. Show that for $ k\equal{}1,2,3,...,n$, the $ k$th tallest husband is at least as tall as the $ k$th tallest wife . (Assume each husband is taller than his wife.)

Not so hard... Since the kth man is taller than his woman and the women of
n-k men who are smaller than him, it follows that the kth man is taller
than at least n-k+1 women. Of course, this means that he must be taller
than the kth tallest woman.


a,b,c is a side
 atriangle

prove

a\(b+c)  +b\(a+c) + c\(a+b) +(a+b)\c +(a+c)\b +(b+c)\a>6

[quote="ashrafmod"]a,b,c is a side
 atriangle

prove

$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+b}+\frac{a+b}{c}+\frac{a+c}{b}+\frac{b+c}{a}>6$[/quote]
You don't need the assumption that $a,b,c$ are sides of a triangle; it sufficies that none of $a,b,c$ is sum of the other two. You just write $\frac{a}{b+c}+\frac{b+c}{a}>2$ and two similar inequalities and sum up.

It is easy to show that $\sum \frac{b+c}{a}\geq 6$
$\sum \frac{a}{b+c}\geq \frac{3}{2}$

try the following triangle ineq :

$(a+b+c)(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}) \geq  6(\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b})$, with $a,b,c$sides of a triangle

 i`ve posted it here somewhere and u reminded me about it. :)


trigonometry
algebra
polynomial
trig identities

observed that

$\cos 18\sin 18\sin 54=\frac{1}{2}\sin 36\sin 54=\frac{1}{4}(\cos 18-\cos 90)$

since $\cos 90=0$ , cancel $\cos 18$ both side and we are done  ;)

Hi. Shyong!

How did you get cos18sin18sin54 from just SIN18SIN54???

And how are we going to cancel cos18 from both sides - I'm from Ukraine and when we are give such tasks we are supposed to solve the left side (sin18sin54), not concerning the whole equation in order to get the result in the right side (1/4).

I didnt start from LHS but instead , i start by simplfying

$\cos 18\sin 18\sin 54$ which gives you $\frac{1}{4}\cos 18$ at last . But since you want to find $\sin 18\sin 54$ , simply divide both side by $\cos 18$ and you will get your answer .

Or if you really want to do it from LHS then just write in this way

$\sin 18\sin 54=\frac{\cos 18}{\cos18}\sin 18\sin 54$ and then simplify it . ;)

I am only 15 y.o. and my preferences are determined by the humanities, not exact science!!! So sometimes it is difficult for me to understand the trigonometry.

Would you be so kind to write the whole task-from the very beginnig!
And I presume you've not understood the way we solve such tasks. I'm giving you an example:

Prove: ctgX-(sinX/(1-cosX))=-(1/(sinX))
Proving: cosX/sinX-(sinX/(1-cosX))=((1-cosX)cosX-sin^2X)/((1-cosX)sinX)=(cosX-cos^2X-sin^2X)/(sinX-sinXcosX)=
(cosX-1)/(sinX(1-cosX))=-(cosX-1)/(sinX(cosX-1))=-(1/(sinX)).

As you see we don't connect the left side of the equation with the right one!!!

First you multiple LHS with $\frac{\cos 18}{\cos 18}$ which you will get

$\sin 18\sin 54=\frac{\cos 18}{\cos 18}\sin 18\sin 54$

Then , using $\sin A\cos A=\frac{1}{2}\sin 2A$ , you get

[hide]$\cos 18\sin18 = \frac{1}{2}\sin 36$
which mean now the expression becomes $\frac{\sin 36\sin 54}{2\cos 18}$
[/hide]

Now we use $\sin A\sin B=\frac{1}{2}(\cos(A-B)-\cos(A+B))$ so we will get

[hide]$\sin 36\sin 54=\frac{1}{2}(\cos 18-\cos 90)$ Again , your expression now is simplified to $\frac{\sin 36\sin 54}{2\cos 18}=\frac{\frac{1}{2}(\cos 18-\cos 90)}{2\cos 18}$ [/hide]

Also we know the fact that $\cos 90=0$ so your expression becomes
[hide] $\frac{\frac{1}{2}(\cos 18-\cos 90)}{2\cos 18}=\frac{\frac{1}{2}\cos 18}{2\cos 18}$  or simply $\frac{1}{4} =RHS$ [/hide]

again, lacking any considerable insight I have had a go and got myself in a mess...

the value of sin(18)sin(54) is equal to 3(sin x)^3 - 4(sin x)^4, where x is the solution to the (insane) polynomial:

0 = 16(sin x)^5 - 20(sin x)^3 + 5(sin x)

which can be simplified, but not factored into any nice number as the discriminant when you divide by sin x is not a square.

this is crazy... I can use euler's formula to find sin(5x) in terms of sin(x) and use trig identities to find sin(x)sin(3x) in terms of sin(x) but can't solve a problem that can be solved in three lines! Just goes to show the maths teaching in the UK is really all about jumping through hoops and nothing more.

Consider a regular pentagon$ABCDE$ with side length $1$, assume that $AD$ meets $CE$ at $F$.
Since the pentagon can be inscribed  in a circle, we have $\angle{ACE}=\angle{ECD}=\angle{CAD}$,denote this by $\theta$, so we can confirm three isosceles triangles $\triangle{ACD}$ with base angle ${2\theta},\ \triangle{CDF}$ with base angle $2\theta$, which are similar, and $\triangle{FAC}$ with base angle $\theta$.Let $x$ be the length of diagonal of the pentagon, we have $CD=CF=AF=1$, since $CF$ is the bisector of $\angle{ACD},$ use the theorem of the biesector of the angle,

we have  $CD: CA=DF: AF \Longleftrightarrow 1: x=(x-1): 1 \Longleftrightarrow x^2-x-1=0$, yielding the length of the diagonal is $x=\frac{1+\sqrt{5}}{2}.$

Now for $\triangle{ACD},$ we have $\angle{CAD}+\angle{ACD}+\angle{ADC}=180^\circ\Longleftrightarrow \theta+2\theta+2\theta=180^\circ,$ yielding $\theta=36^\circ.$
Now remark the isosceles $ABE$ with base angle $36^\circ$, let $AH$ be the altitude of the triangle, we obtain

$\cos 36^\circ=\frac{BH}{AB}=\frac{\text{the half length of the diagonal}}{1}=\frac{1+\sqrt{5}}{4}.$ Analogously remark the isosceles $ACD$ with base angle $72^\circ$,

let $AK$ be the altitude of the triangle, we obtain the right triangle $ACK$ with $\angle{CAD}=18^\circ.$ thus we have

$\sin 18^\circ=\frac{CK}{AC}=\frac{\text{the half length of the side length of the pentagon}}{\text{the length of the diagonal}}=\frac{\sqrt{5}-1}{4}.$

Therefore desired answer is $\sin 18^\circ \sin 54^\circ=\sin18^\circ \cos 36^\circ=\boxed{\frac{1}{4}}.$

kunny

:)  THANKS TO: [u]kunny and degreestudent[/u] but your explanations  are very, very, very complicated!!! I don't know either euler's formula, nor kunny's method. We are not teached in that intense way in a humble school in Ukraine!

And my special thank to [u]shyong[/u]. At last I got what I wanted in your last message!

I just feel I'm getting cleverer!   :lol: [/b]

glad I helped! basically, cos(nx) + i sin (nx) = (cos x + i sin x)^n. as the value of i^n oscillates between i, -1, -i, 1, for increasing powers of n, you can use the binomial expansion to find the solution for large(ish) values of n, and the simply equate real and imaginary parts to find the formula of cos(nx) and sin(nx) respectively. There are much better explanations on the internet though! I just spotted that 18 = 3*54 and 18*5 = 90, and we know sin 90 = sin(5*18) = 0.

This problem's point is associating the regular polygon with $18^\circ\ times\ natural\ number$ with regular pentagon and [b]Golden section[/b]. Thus best solution is using geometry. ;)

[quote="pupOK"]Hi! It's me again. I have a wee bit of a problem  :oops:
My teacher proposed me to solve that task, considering that:
sin3X=3sinX-4sin^3X, hence
sin54=sin3*18=3sin18-4(sin^3)18[/quote]That's what I was trying to get at... have you learnt the formula for the expansion of (cos@ + i sin@)^n ?


Prove that the sequence $ (a_n)_{n \geq 0,}, a_n \equal{} [n \cdot \sqrt{2}],$ contains an infinite number of perfect squares.

I think that it is an easy corollary of this:

Let $ \alpha\in\mathbb{R}$ be a non rational number. We define A this way:

$ A \equal{} \{\{\alpha n^2\}\; |\; n\in\mathbb{N}\}$ where $ \{ x\} \equal{} x \minus{} [x]$

Then A is dense over (0,1)

Proof of this fact:

For every t>0 we can partition (0,1) in a finite number of intervals such that the lenght of each interval is smallest then $ \frac t 4$

We associate to each interval a colour (different interval==>different colour). Then we colour every natural number n of the same colour that we associated to the interval which $ \{\alpha n^2\}$ belongs to. By Van Der Waerden (probably this is not the right spelling) theorem there are three natural numbers of the same colour in an arithmetic progression. If we call this three number a-b, a, a+b, since $ 4b^2 \equal{} 2(a \minus{} b)^2 \plus{} 2(a \plus{} b)^2 \minus{} 4a^2$ we have that  $ \{ 4b^2\alpha\} \in (0,t)\cup (1 \minus{} t,1)$

Without loss of generality $ \{ 4b^2\alpha\} \in (0,t)$

Let's call $ \{ 4b^2\alpha\} \equal{} s$ for practical reasons.

Now, let's consider a general interval (c,d) with $ 0\le c < d\le 1$

We take $ k\in\mathbb{N}$ such that $ ks < d\le (k \plus{} 1)s$

Let's say $ k \equal{} q^2 \plus{} r$ with $ 0\le r\le 2q$

Now clearly $ q^2 s < d$

Furthermore $ (q^2 \plus{} r \plus{} 1)s\ge d$ so $ q^2s\ge d \minus{} (r \plus{} 1)s\ge d \minus{} (2q \plus{} 1)s > d \minus{} 2\sqrt {ds} \minus{} s$ which is greater than c for s small enough, so $ \{ (2bq)^2\alpha\}\in (c,d)$ and we are finished.

I hope it is clear enough...


function
integration
calculus
real analysis
abstract algebra
real analysis unsolved

Suppose we are working in $ \mathbf R^n$. Find Fourier transform (in the sense of $ \mathcal S'(\mathbf R^n)$) of the function $ f(x) \equal{} |x|^{ \minus{} \alpha}$, $ 0 < \alpha < n$.

I like this calculation so much I wrote it up in the notes for the course I teach.

Since you didn't specify a "where to put the $ 2\pi$" convention for the Fourier transform, I'll use my own preferred convention:
\[ \widehat{f}(\mathbf{s})\equal{}\int_{\mathbb{R}^n}f(\mathbf{x})
e^{\minus{}2\pi i\mathbf{s}\cdot\mathbf{x}}\,d\mathbf{x}.\]
We start with this calculation:

The Fourier transform of $ e^{\minus{}\pi u|\mathbf{x}|^2}$ is $ u^{\minus{}n/2}e^{\minus{}\frac{\pi|\mathbf{s}|^2}{u}}.$

Now try forming a "linear combination" of the functions $ e^{\minus{}\pi u|\mathbf{x}|^2}$ indexed by $ u>0$ as follows:

$ \int_0^{\infty}u^ce^{\minus{}\pi u|\mathbf{x}|^2}\,du\equal{}
\pi^{\minus{}(c\plus{}1)}|\mathbf{x}|^{\minus{}(c\plus{}1)}\int_0^{\infty}v^ce^{\minus{}v}\,dv\equal{}
\frac{\Gamma(c\plus{}1)}{\pi^{c\plus{}1}|\mathbf{x}|^{2(c\plus{}1)}}.$

Now let $ c\equal{}\frac{\alpha}2\minus{}1.$

$ f(|\mathbf{x}|)\equal{}|\mathbf{x}|^{\minus{}\alpha}\equal{}\frac{\pi^{\alpha/2}}
{\Gamma(\alpha/2)}\int_0^{\infty}u^{\frac{\alpha}2\minus{}1}
e^{\minus{}\pi u|\mathbf{x}|^2}\,du$

(Thought of as a linear combination of Gaussian functions, this integral does converge in the sense of distributions.) So,

$ \widehat{f}(\mathbf{s})\equal{}\frac{\pi^{\alpha/2}}
{\Gamma(\alpha/2)}\int_0^{\infty}u^{\frac{\alpha}2\minus{}\frac{n}2\minus{}1}
e^{\minus{}\frac{\pi |\mathbf{s}|^2}{u}}\,du$

Now let $ v\equal{}\frac{\pi|\mathbf{s}|^2}u$ so that $ u\equal{}\frac{\pi|\mathbf{s}|^2}u$ and $ du\equal{}\frac{\pi|\mathbf{s}|^2}{v^2}\,dv:$

$ \widehat{f}(\mathbf{s})\equal{}\frac{\pi^{\alpha/2}\pi^{(\alpha\minus{}n)/2}}
{\Gamma(\alpha/2)|\mathbf{s}|^{n\minus{}\alpha}}
\int_0^{\infty}v^{\frac{n}2\minus{}\frac{\alpha}2\minus{}1}e^{\minus{}v}\,dv$

$ \equal{}\frac{\pi^{\alpha\minus{}\frac{n}2}\Gamma\left(\frac{n\minus{}\alpha}2\right)} {\Gamma\left(\frac{\alpha}2\right)}\cdot|\mathbf{s}|^{\minus{}(n\minus{}\alpha)}.$

What is the fundamental solution for the Laplacian? We can use this to solve Poisson's equation in $ \mathbb{R}^n: \ \nabla^2u \equal{} \rho.$ The fundamental solution is the distribution $ K$ such that $ \nabla^2K \equal{} \delta.$ Once we have that, we may obtain the solution to the PDE by convolution: $ u \equal{} K*\rho.$

But if we take the Fourier transform of $ \nabla^2K \equal{} \delta,$ we get $ \minus{} 4\pi^2|\mathbf{s}|^2\widehat{K}(\mathbf{s}) \equal{} 1,$ so that $ \widehat{K}(\mathbf{s}) \equal{} \frac { \minus{} 1}{4\pi^2|\mathbf{s}|^2}.$

The computation above gives us $ K,$ which is also known as the "Newtonian potential." All we have to do is to set $ n \minus{} \alpha \equal{} 2,$ and to multiply by the appropriate constants.

However, we do note (and it's implied the restrictions on the original problem) that this only works for $ n\ge 3.$ It doesn't work for $ n \equal{} 2;$ that case will require a different computation.

In the particular case of $ n\equal{}3,$ the computation above gives that the Fourier transform of $ \frac1{|\mathbf{x}|}$ is $ \frac1{\pi|\mathbf{s}|^2}$ so that the Newtonian potential in $ \mathbb{R}^3$ is
\[ K(\mathbf{x})\equal{}\frac{\minus{}1}{4\pi|\mathbf{x}|}.\]

This is a quite tricky solution, indeed. I saw it in a Stein's book. The "direct approach" seems to be not fruitful here.

[quote="volodja"]I saw it in a Stein's book.[/quote]
That's essentially where I know it from - I belong to that "family" of mathematicians.

[quote]The "direct approach" seems to be not fruitful here.[/quote]
There are several difficulties, one of which is that the function is not in $ L^1$ or $ L^2.$ You wrote "in the sense of tempered distributions" in your original statement - you had to say that.

A followup (The Poisson kernel in $ \mathbb{R}^n$):

Use the fact that in one dimension, the Fourier transform of $ \frac{1}{\pi(x^2\plus{}1)}$ is $ e^{\minus{}2\pi|s|},$ and this method to find the function in $ \mathbb{R}^n$ whose Fourier transform is $ e^{\minus{}2\pi|\mathbf{s}|}.$


function
inequalities
inequalities unsolved

It is not too hard. After multipliing the terms you get:

$a^2b^2c^2+\sum_{cyclic}\frac{b^2c^3}{a}+\sum_{cyclic}\frac{b^3}{a}\geq 124$.

After appliing AM-GM for the sums we have only to show:

$(abc)^2+3(abc)^{\frac{2}{3}}+3(abc)^{\frac{4}{3}}\geq 124$.

The left side is an increasing function in $abc$ so we only have to check the inequality for $abc=8$ for which we get the equality.

Misha


[color=yellow]2pi-4[/color] b/c diameter of circle is 4 (1/2 of 8) (4/2)^2pi/2=[color=yellow]2pi-4[/color](area of small triangle)

[hide]
The diameter of the circle is 4, since $ PB$ is also an altitude. We want to find the area of the little parts of the circle outside the triangle. Each of these is a quarter circle minus an isosceles right triangle. The area of the quarter circle is $ \frac {4\pi}{4} \equal{} \pi$, and each leg of the triangle is a radius, so each leg is 2, so the area is 2. Each little part is $ \pi \minus{} 2$, there are 2 of them. Answer: $ 2(\pi \minus{} 2) \equal{} 2\pi \minus{} 4$[/hide]


Can anyone give me some ideas of what i should write about snowflake Geometry.

[b]Task: You are required to give a 3 to 4 minute lecturette on the topic you have selected. (more like randomly choosen), which is SnowFlake Geometry.
[/b]
Marks will be awarded as:
Content: 10
Ideas presented in logical order:4
Clarity of presentation:3
Presentation:3

I need some ideas of what i should put into this presentation about snowflake geometry.
Help will be appreciated.

Do you mean something like folding a piece of paper in eighths and cutting things out of it? If so, you can discuss symmetry, the effects of cutting from different sides (on the design), etc. Another idea is to take a snowflake and fold it in such a way that you can look at what was cut out, multiply by a certain power of 2, and determine the area.

I wish we had such fun math projects! But no, instead we have the evil "Let's Dance!", which I did last year, or "Bits and Pieces" (which I personally never did)!

[quote="SnowStorm"]You are talking about the geometry of snow right, like the kind that falls outside?  Not some weird aspect of math I've never heard of? lol

Anyway,
Symmetry is pretty much the only thing I can think of.[/quote]

yep snowflake geometry like this [code]http://www.earthmatrix.com/snowflake/snowflak.htm
[/code]

The link doesn't work, but I think you can still use what I said. Try looking up sites on kirigami.


For $ n \in \mathbb{N}$ , $ n \geq 2$ we define  $ x_{n}\equal{}\sqrt{2\plus{}\sqrt[3]{3\plus{}\sqrt[4]{...\plus{}\sqrt[n]{n}}}}$.Prove that the sequence $ (x_{n})_{n\geq 2}$ converges to a limit $ x$  and:
\[ x\minus{}x_{n}\leq \frac{2}{n!}\]

Herschfeld's convergence theorem may help for convergence of $ x_n$. :)

See also shortlist for IMO problems 1985


http://www.mathlinks.ro/Forum/viewtopic.php?t=91184

Why are marathons disliked now?

Disadvantages:
1) It's hard to search problems
2) Lack of discussions
3) Varies with difficulty (usually scales off to higher difficulty and therefore harder for moderators/admins to move topics to appropriate forum)
4) Topics grow disproportionate
5) Spams

Advantages:
1) Popular thing and fun
2) "It feels like home"
3) Sort of categorized within the same thread the same type of problems like "Which is bigger?" and "Intermediate Geometry"
4) Great place for you to show off
5) "I don't like boring discussions"

That's it for now, you can add other stuff, criticize, whatever ... this is The Round Table after all. :D

Well the disadvantages are true... maybe it's better to post lonely problems after all


If a twelve-hour clock strikes once at 1 o'clock, twice at 2 o'clock, and so on, so that it strikes a number of times equal to the hour, how many times will it strike in one day?

It's just the sum of the first 12 integers doubled, because it's two 12 hour periods. This is $ \frac {12*13}{2}*2\equal{}\boxed {156}$

I love this problem

Because there are 2 twelve-hour periods in a day, its just the sum of the numbers 1 to 12, times 2.

78 $ \cdot$ 2=156, our answer


let $ a,b,c$ are non-negative.prove that:
$ 15(a^2b \plus{} b^2c \plus{} c^2a)\plus{}3abc \le 4(a^3 \plus{} b^3 \plus{} c^3) \plus{} 12(ab^2 \plus{} bc^2 \plus{} ca^2)$

[quote="tuantam1lan"]let $ a,b,c$ are non-negative.prove that:
$ 5(a^2b \plus{} b^2c \plus{} c^2a) \le (a^3 \plus{} b^3 \plus{} c^3) \plus{} 4(ab^2 \plus{} bc^2 \plus{} ca^2)$[/quote]

This inequality isn't true..Try:$ c \equal{} 0;a\equal{}3; b \equal{} 1$
 :P

Your counterexample is wrong^^
But there are some others. Try for instance $ c\equal{}0$, $ b\equal{}1$, $ a\equal{}3$ to get a contradiction.

[quote="FelixD"]Your counterexample is wrong^^
But there are some others. Try for instance $ c \equal{} 0$, $ b \equal{} 1$, $ a \equal{} 3$ to get a contradiction.[/quote]
Thanks you..I edited.:P.But This inequality is wrong  :)

[quote="caubetoanhoc94"][quote="tuantam1lan"]let $ a,b,c$ are non-negative.prove that:
$ 5(a^2b \plus{} b^2c \plus{} c^2a) \le (a^3 \plus{} b^3 \plus{} c^3) \plus{} 4(ab^2 \plus{} bc^2 \plus{} ca^2)$[/quote]

This inequality isn't true..Try:$ c \equal{} 0;a \equal{} 3; b \equal{} 1$
 :P[/quote]
thank you very much!
i'm sorry for my mistake
i repaired problem


abstract algebra
linear algebra
matrix
Ring Theory
superior algebra
superior algebra unsolved

Must be classical but I didn't find it on this forum
For $n,m \in \mathbb{N}^{*}$, find out $|\mathrm{GL}_{n}(\mathbb{Z}/m\mathbb{Z})|$ and $|\mathrm{SL}_{n}(\mathbb{Z}/m\mathbb{Z})|$.

For a commutative ring $R$, we define

$\mathrm{GL}_{n}(R) : = (R^{n \times n})^{*}= \{A \in R^{n \times n}: \det(A) \in R^{*}\}$
$\mathrm{SL}_{n}(R) : = \{A \in \mathrm{GL}_{n}(R) : \det(A) = 1\}$

[b]1.[/b] $\mathrm{GL}_{n}(R) / \mathrm{SL}_{n}(R) \cong R^{*}$

Proof: $\det$ is an epimorphism $\mathrm{GL}_{n}(R) \to R^{*}$ with kernel $\mathrm{SL}_{n}(R)$.

[b]2.[/b] $|\mathrm{GL}_{n}(\mathbb{F}_{q})| = (q^{n}-1)*(q^{n}-q)*\cdots*(q^{n}-q^{n-1})$

Proof: The first column of a matrix in $\mathrm{GL}_{n}(\mathbb{F}_{q})$ can be anything but $0$; so there are $q^{n}-1$ possibilities. The column $i$ can be anything not lying in the subspace generated from the previous columns, which has dimension $i-1$. So there are $q^{n}-q^{i-1}$ possibilities.

[b]3.[/b] (by Gockel) Let $R$ be a commutative local ring with maximal ideal $\mathfrak{m}$ and residue field $K = R / \mathfrak{m}$ . Then

$|\mathrm{GL}_{n}(R)| = |\mathfrak{m}|^{n^{2}}* |\mathrm{GL}_{n}(K)|$

Proof: The projection $\pi : R \to K$ yields pointwise $\psi : R^{n \times n}\to K^{n \times m}$, both surjective homomorphisms of rings with $\ker(\pi) = \mathfrak{m}$ and hence $\ker(\psi) = \mathfrak{m}^{n \times n}$. Since $R$ is local, $R \backslash M = R^{*}$. Thus, for all $A \in R^{n \times n}$, we have

$\psi(A) \in GL_{n}(K) \Leftrightarrow 0 \neq \det(\psi(A)) = \phi(\det(A)) \Leftrightarrow \det(A) \notin M \nolinebreak\Leftrightarrow \nolinebreak\det(A) \in \nolinebreak R^{*}\Leftrightarrow \nolinebreak A \in \nolinebreak GL_{n}(R)$

This shows $\mathrm{GL}_{n}(R) = \psi^{-1}(\mathrm{GL}_{n}(K))$. Then every element of $\mathrm{GL}_{n}(K)$ has exactly $|\ker(\psi)| = |\mathfrak{m}|^{n^{2}}$ preimages under $\psi$, and the claim follows.

[b]4.[/b] $\mathrm{GL}_{n}(R \times S) \cong \mathrm{GL}_{n}(R) \times \mathrm{GL}_{n}(S)$

Proof: Too obvious ;-).

Now, we can calculate the order of $\mathrm{GL}_{n}(\mathbb{Z}/m)$. First, if $m = p^{k}$, $\mathbb{Z}/p^{k-1}$ is the unique maximal ideal of $\mathbb{Z}/p^{k}$ with residue field $\mathbb{F}_{p}$. Hence, applying 3. and 2., we get

$|\mathrm{GL}_{n}(\mathbb{Z}/p^{k})| = (p^{k-1})^{n^{2}}|\mathrm{GL}_{n}(\mathbb{F}_{p})| = p^{n^{2}(k-1)}* (p^{n}-1)*...*(p^{n}-p^{n-1})$

Combining this with 4., we get the general order for $m = p_{1}^{k_{1}}*\cdots * p_{r}^{k_{r}}$. Since $\mathbb{Z}/m \cong \mathbb{Z}/ p_{1}^{k_{1}}\times \cdots \times \mathbb{Z}/p_{r}^{k_{r}}$ , we have

$|\mathrm{GL}_{n}(\mathbb{Z}/m)| = |\mathrm{GL}_{n}(\mathbb{Z}/p_{1}^{k_{1}})|* \cdots * |\mathrm{GL}_{n}(\mathbb{Z}/p_{r}^{k_{r}})|$

Finally, 1. implies

$|\mathrm{SL}_{n}(\mathbb{Z}/m)| = |\mathrm{GL}_{n}(\mathbb{Z}/m)|/\phi(m)$


function
induction
algebra unsolved
algebra

Find all functions $f: \mathbb{R}\to\mathbb{R}$ such that
\[[f(x)]^{2}=1+xf(x+1),\]
for all real $x$.

[quote="behemont"]Find all functions $f: \mathbb{R}\to\mathbb{R}$ such that:
$[f(x)]^{2}=1+xf(x+1)$.[/quote]

There is an infinite number of solutions.
Here is a way of constructing such solutions.

1) Choose any function $u(x)$ defined for $x\in[0,1]$ and such that $u(0)=1$ or $-1$ and $u(x)\leq\frac{1}{1-x}$ $\forall$ $x\in[0,1)$
2) Choose any function $v(x)$ defined for $x<0$ and such that $v(x)\in\{-1,+1\}$ $\forall x<0$

Then you can define $f(x)$ thru induction :
a) For $x\in[0,1]$, $f(x)=u(x)$
b) For $x>1$, $f(x)=\frac{(f(x-1))^{2}-1}{x-1}$
c) For $x<0$ :
c.1) if $1+xf(x+1)\leq\frac{1}{(x-1)^{2}}$ then $f(x)=v(x)\sqrt{1+xf(x+1)}$
c.2) if $1+xf(x+1)>\frac{1}{(x-1)^{2}}$ then $f(x)=-\sqrt{1+xf(x+1)}$

The lmportant thing of this construction is the fact that we always have $1+xf(x+1)\geq 0$ $\forall x$


Let $ a,b,c$ be positive real numbers such that $ a\plus{}b\plus{}c\equal{}3$. Prove that
$ \frac{1}{2}\sum\limits_{cyc}\frac{a^2}{b^2\plus{}c^2}\ge \frac{9\minus{}ab\minus{}bc\minus{}ca}{(a\plus{}b)(b\plus{}c)(c\plus{}a)}$

[quote="The soul of rock"]Let $ a,b,c$ be positive real numbers such that $ a \plus{} b \plus{} c \equal{} 3$. Prove that
$ \frac {1}{2}\sum\limits_{cyc}\frac {a^2}{b^2 \plus{} c^2}\ge \frac {9 \minus{} ab \minus{} bc \minus{} ca}{(a \plus{} b)(b \plus{} c)(c \plus{} a)}$[/quote]
Using the known inequality
\[ \sum \frac{a^2}{b^2\plus{}c^2} \ge \sum \frac{a}{b\plus{}c}\]
It suffices to prove that
\[ \sum \frac{a}{b\plus{}c} \ge \frac{18\minus{}2(ab\plus{}bc\plus{}ca)}{(a\plus{}b)(b\plus{}c)(c\plus{}a)}\]
which is equivalent to
\[ \sum a(a\minus{}b)(a\minus{}c) \ge 0\]
This is Schur's Inequality. :)


In how many ways can you form $ 3$ pairs of people from a group of $ 6$ people?

[hide="pretty common"] $ \binom{6}{2}\cdot\binom{4}{2}\cdot\binom{2}{2}$, but this considers each pair separate, so we divide by $ 3!$, giving $ 15\cdot6\cdot1\cdot\frac {1}{6}\equal{}15$.[/hide]

There are C(6,2)=15 ways to choose the first pair, C(4,2)=6 ways to choose the second pair, and C(2,2)=1 way to choose the last. But the order the pairs are assigned doesn't matter, so we need to divide by 3!=6. So the number of ways to pair the people is $ \frac{15*6}{6}\equal{}\boxed{15}$ ways.

EDIT: Beaten


a barrel in the shape of a circular cylinder that is to hold 50 gallons. find the h[color=darkred]eight[/color] of the barrel and the r[color=darkred]adious[/color] of the base of the barrel that may be built using the least amount of material. Note: 1 Gallon = 231 Cubit Inches

formulas needed: V= pi*r^2*h and SA: 2pirh+2pir^2

please help... thanks[/img][/hide]

Dude... that post is a wreck...

Anyway, so you know that $rh = (50)(231) \implies h = \frac{(50)(231)}{r}$.

So now you can substitute that into the formula for the total surface area ... can you make a quadratic out of this?


What purpose is served by cutting the onion into
very small pieces?

hi, why is it important to cut the onions into small pieces when trying to extract DNA

thank you

-titan

When extracting DNA, the cells lyse, allowing the DNA to come out of the nucleus. Cutting the onion into small parts exposes more cells, so more cells lyse and you can get more DNA.


algebra
function
domain
LaTeX
geometry
3D geometry
complex numbers

(1) $\sqrt[3]{t-1}$ we have $t \in R$.

(2) $\sqrt{\dfrac{2+x}{3-x}}$. Since it is square root instead of cube root, so we will have: $(2+x)(3-x) \geq0$ and $3-x \neq 0$. Which gives: $-2 \leq x < 3$.

[quote="g3pilotplaya"]My teacher told me the rule about htis one but i forgot it.

Directions: Find the domain of this equation-       the cubed root of ( t - 1)

THe next problem is to find the domain as well -   sqrt of ( 2 + x)/(3-x)

sry cant do latex yet.[/quote]

Remember the rules:

- The domain of a cubed root always belongs to $R$
- The number under the square root must be $\ge{0}$ (Not mention the complex numbers)
- The denominator is different from 0


How to prove that (0;0) is only one integer solution of this equation?

It's kind of obvious: every power of 3 yields an odd number while every power except 0 of 2 yields an even number.  So the only time they can agree is when they're both 1, or at $ (m,n)\equal{}(0,0)$.

Thay are not neccesary integers, for example $ 2^{\minus{}3}\equal{}\frac{1}{8}$

[hide="hint"]prove that $ \log_3{2}$ or $ \log_2{3}$ is irrational.[/hide]

[quote="Bachukas"]Thay are not neccesary integers, for example $ 2^{ \minus{} 3} \equal{} \frac {1}{8}$[/quote]

[quote="Bachukas"] How to prove that (0;0) is the only [b]integer[/b] solution of this equation? [/quote]

???

He means that $ n, m$ are integers but $ 2^n, 3^m$ are not necessarily integers.  But this is irrelevant:  exactly one of the identities

$ 2^n \equal{} 3^m$
$ 2^n 3^{ \minus{} m} \equal{} 1$
$ 2^{ \minus{} n} 3^m \equal{} 1$
$ 2^{ \minus{} n} \equal{} 3^{\minus{}m}$

is an integer identity.

Now, since one of those four identities is an integer identity, the rest of the problem can be easily deduced because g.c.d. $ (2,3)\equal{}1$


modular arithmetic
number theory unsolved
number theory

Express the number 1988 as the sum of some positive integers in such a way that the product of these positive integers is maximal.

Similar to IMO 1976 Day 2 Problem 1 [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?p=367432&sid=fdc51aacc9b1da5e5ceecd38ace2ff10#p367432[/url]
If $a$ occurs in the product and $a \geq 4$, we can replace $a$ by $2$ and $a - 2$, since then the sum remains constant and the product increases (as $2(a - 2) \geq a$).

Hence we may assume that we are using only $2$'s and $3$'s. Now, since $2^3 < 3^2$, we need to use as many $3$'s as possible. Since $1988 \equiv 2 \pmod{3}$, we can use $1986/3 = 662$ times $3$ and we can use $2$ once, giving a product of $2 \cdot 3^{662}$.


I was bored today so I was just searching up random things and I found [url=http://www.travelpod.com/traveler-iq]The Traveler IQ Challenge[/url].

For me, this was a pretty fun game and I spent quite a bit of time on it.

The only score that I'm sure of (when I actually started keeping track) was making it to level 8 on World (World Capitals, Hard) and then missing by a couple thousand points...which gave me an IQ of 100  :lol: .

There are several other challenges as well, and the USA Challenge seemed a lot easier...I wonder why.

Anyway I just wanted to throw this out there for anyone who has time to waste.

EDIT: Level 6 on USA because I have no clue where all this random cities are...

On my first try I got something like level 6 with an IQ of 93.

I'll try again.  :)

I think I got to level 6 as well the first time I did it, but I learned quite a lot in just a few tries  :) . Unfortunately, I've now made level 8 several times in a row, but I don't know very many African countries, so I keep losing.

On the other hand, I just made it to level 11 on Asia  :) . Lost by 3000.

EDIT: Made it to level 10 on World, finished with 369562, IQ of 110.
EDIT2: Still made it to level 10 on World again, finished with 377,131, IQ of 111. I dunno why I said this even though it didn't change much, but I feel proud  :P .
EDIT3: Level 7 of 8 on World Capitals, died on Caribbean, 115 IQ.
EDIT4: Level 12 of 14 on the UNESCO thing, 107 IQ...seriously level 12 is impossible. Anyway who can pass that is a beast. Oh and 382.6K on World, still level 10, 112 IQ. Temperal keeps beating my score. Darn.

I think I failed on level 9 or 10. I got 110.

Oh dang what it kicks you out if you fail? I finished the game, I just can't remember my score!

Lolz...I'm so fail. Hopefully I'll do better on my second try. I did get within 10 km for Muscat, Oman, though...yay. My worst is about 6000 km for some Russia one.

I got level 8 on my 2nd try, with also a 100 IQ. This test is really off imo. It should be raised like 10 points all around.

Also, it would be so much better if I had 5 more seconds to think (without having me lose points) on each one, I could do so much better that way.

Hm I think I clicked within 5 km of Trinidad and Tobago.

My closest is 6 km from Los Angeles. I got my closest to Level 11 on this random try at 12:37 AM because I couldn't sleep so I decided to do some math and then got tired and just felt like playing. I was 2104 away. Darn. I will go do something else today.

I could only get to level 8, with an IQ of 97 (who cares where these places are?)

On a side note, this is a rip-off of Globetrotter XL... or maybe Globetrotter XL is a rip-off of THIS.

i missed lisbon, portugal by 19 km.
and then i left the computer and got owned. so then i tried again, missed machester england by 15km and nagoya japan by 15 km, and got an IQ of 101

i missed a level by like 100 points :wallbash_red:
got IQ of 101 but i'm not very good at this
i clicked on east coast for something in hawaii...LOL (8000+ km off)

On the world, I got to level 8, and got an IQ of 102

For the U.S, I got to level 6 and an IQ of 105

On world I got to level 6 with an IQ of 93 and an unknown score.


analytic geometry
graphing lines
slope
conics
ellipse
geometry

Let the equation of an ellipse be $\frac{x^{2}}{4}+\frac{y^{2}}{12}=1$ .
$A(1,3),B,C$ are three points located on the ellipse such that $ABC$ is isosceles triangle with $AB=AC$ . Find the slope of $BC$ .

I can't prove it, but it appears that $B$ and $C$ will always lie on one of the lines $y =-\frac{1}{3}x+k$ (perpendicular to the line from $A$ to the center of the ellipse).


$a,b,c$ are positive real numbers such that $a+b+c=3$ prove that :

$a^{3}+b^{3}+c^{3}+2abc \geq 5$


function integration probability calculus logarithms parameterization inequalities

$E$ the set of positive measurable functions $f: \mathbb{R}\to \mathbb{R}^+$ satisfying:
1/ $\int_{-\infty}^{+\infty}f(x)dx=1$
2/ $\int_{-\infty}^{+\infty}xf(x)dx=0$
3/ $\int_{-\infty}^{+\infty}x^2f(x)dx=1$
(i.e. density of probability with null mean and unit deviation).
One can define $H(f)=-\int_{-\infty}^{+\infty}f(x)ln(f(x))dx$ if this integral exists, and $+\infty$ otherwise.
Find the function of $E$ that minimizes $H$.

Just to confirm, are you sure you want to minimize entropy?  Or did you want to maximize?

I'm pretty sure that the Gaussian maximizes entropy, not minimizes.  I was posting my proof of that result before I realized that the question was asking for minimization.  :blush:

I was assuming that $f(x) \ln f(x)$ would be treated as 0 when $f(x) = 0$, which is the usual assumption in information theory.  Besides, doesn't the problem say that $f$ is everywhere positive?

you are right, the gaussian maximizes.

to see that $\inf_{f\in E}H(f)=-\infty$, let

$f_n(x)=\begin{cases}b, &|x|\leq 1\\ ax^{-2n}, &|x|>1\end{cases}$.

with the constants $a$, $b$ such that $\int x^jf_n(x)dx=1$, $j=0,2$. It turns out that $b=\frac{3}{4n}$ and $a=n+O(1)$.

Then $H(f_n)=-\log n+O(1)$ as $n\to-\infty$.

Okay.  I didn't check the details, but your counterexample looks convincing.

[quote="cimabue"]ok, i guess you are right about  vanishing set, i rushed through. so far:

it looks like $\inf_{f\in E}H(f)=-\infty$.

to see this: for $n\geq 1$, let $f_n(x)=\begin{cases}b, &|x|\leq 1\\ ax^{-2n}, &|x|>1\end{cases}$.

with the constants $a$, $b$ such that $\int x^jf_n(x)dx=1$, $j=0,2$. It turns out that $b=\frac{3}{4n}$ and $a=n+O(1)$.

Then $H(f_n)=-\log n+O(1)$ as $n\to-\infty$.[/quote]
$H(f_n)=1+o(1)$ in your example. Anyway, Gaussian is the only maximum.

[quote="cimabue"]it must be the gaussian $f(x)=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}$, $H(f)=\frac{1}{2}(1+\log(2\pi))$.

question: what is the reason for calling $H$ the entropy?[/quote]
Learn some information theory. Basically it's because up to a mult. constant, $x \ln x$ is the only function satisfies some "natural" conditions.

i stand by my claim. i think it should be quite difficult in this context to find non-trivial one-parameter families of functions with bounded entropy.

Here is my proof that the Gaussian maximizes entropy.

Let $g$ be an arbitrary probability density function.  Then it is known (and easy to show) that entropy obeys the inequality
\[ H(f) \le - \int_{-\infty}^\infty f(x) \ln g(x) \, dx.  \]
Equality holds iff $f$ is equal to $g$ almost everywhere.

To optimize this bound, let $g$ be the Gaussian density as cimabue defined.  Then
\[ - \ln g(x) = \frac{x^2}{2} + \ln \sqrt{2\pi} \, .  \]
Because $f$ has standard deviation $1$, we have
\[ H(f) \le - \int_{-\infty}^{\infty} f(x) \ln g(x) = \frac{1}{2} + \ln \sqrt{2 \pi} \, .  \]
The right-hand side is the entropy of the Gaussian, as cimabue calculated.  Thus the Gaussian maximizes entropy, and is unique up to measure zero.

Note that the proof didn't require that $f$ has zero mean.


You have $ n$ silver coins, one of which is fake and therefore weighs a slightly different amount than the other six coins. In order to find out which of the coins is the counterfeit, you have a two-pan balance scale, where you can load items in each of two pans and pres a button the scale and the scale will tell you if the items in the two pans weighs the same amount and if they do not, which pan is heavier. What is the minimum number of button-presses, in terms of $ n$, you need to completely determine which of the coins is counterfeit?

There was a post similar to this not too long ago.  Use the search feature to try to find it.

I know, but this generalizes that post titled "pairwise comparisons". Hence, the name of this post...


Integers $ a,$ $ b,$ $ c,$ and $ d,$ not necessarily distinct, are chosen independantly and at random from $ 0$ to $ 2007,$ inclusive. What is the probability that $ ad \minus{} bc$ is even?

$ \textbf{(A)}\ \frac {3}{8}\qquad \textbf{(B)}\ \frac {7}{16}\qquad \textbf{(C)}\ \frac {1}{2}\qquad \textbf{(D)}\ \frac {9}{16}\qquad \textbf{(E)}\ \frac {5}{8}$

[hide="Solution"]
There are an equal amount of even and odd integers between 0 and 2007, inclusive (zero is usually considered even).

The value of $ad-bc$ will be even iff both $ad$ and $bc$ are odd, or both are even.

For a product to be odd, both of the factors need to be odd.

Thus, for the case where both products are odd, the probability is
$\left(\frac{1}{2}\cdot \frac{1}{2}\right)$ that one of the products is odd, and $\frac{1}{16}$ that both products are odd.

For the case where both products are even, we see that we can have an even product as long as both factors are not odd, or $\frac{3}{4}$ of the time. The probability of having two of these is $\left(\frac{3}{4}\right)^{2}$

The sum of these probabilities is
$\frac{1}{16}+\frac{9}{16}$
$\frac{10}{16}$
$\frac{5}{8}$

Answer choice (E).
[/hide]

Oh!
 I forgot the 1/16 added at the end  :(

Another case by case analysis...  Sadly, I got D instead of E because apparently 9+1=9...

[hide]
0 will be odd, E will be even.
Sums:  E+E=E
E+O=O
O+O=O

Products: E(E)=E
E(O)=E
O(O)=O

So, we have several cases to consider

a-E
b-E
c-E
d-E
The final outcome will be even, and there is one way to do this.

a-E
b-E
c-E
d-O
The final outcome will be even, and there are 4 ways to do this.

There are two cases when there are 2 Es and 2 Os, one in which the Os are grouped together in a product and one in which they are not.
a-E
b-E
c-O
d-O
The final outcome will be odd, and there are 2 ways to do this.

a-E
b-O
c-E
d-O
The final outcome will be even, and there are 4 ways to do this.

a-E
b-O
c-O
d-O
The final outcome will be odd, and there are 4 ways to do this.

a-O
b-O
c-O
d-O
The final outcome will be even, and there is only 1 way to do this.

The probability that the outcome is even is $(1+4+4+1)/(1+4+4+4+2+1)$, or $5/8$

The answer is $E$[/hide]

That seems long and unwieldy to the casual observer, but in reality, it's exactly what I did. I think that it's faster sometimes to note that the product of two numbers of equal parity is always even, and the product of two numbers of inequal parity is always odd.

My solution was too long (there is always a nicer, shorter one).  However, it didn't take that long even to write out, but I don't feel comfortable enough with my probability and combinatorics to do problems more complicated than that using shortcuts...

the probability of "ad-bc is odd" : ad - odd, bc - even and vice versa. So, the probability of "ad - odd" equals 1/4(both a and d odd) then the probability of "bc-even" equals 3/4(either both numbers even - 1/4, or one of them even and the other odd - 1/2) that yields to 1/4*3/4=3/16, and taking into account symmetric case (ad - even and bc - odd) 6/16.

No, the probability of "ad-bc" is even equals 1-6/16=5/8.

[hide="Solution"]
===============================

There are 2 cases for this to happen.

[b]Case 1:[/b]
Both of $ad$ and $bc$ are even.
For one of them to be even, $a$ or $d$ is even so the probability that $ad$ is even is:
$$ 1-\frac{1}{4}=\frac{3}{4} $$
Similarly $bc$ can be computed using the same method.
So:
$$ \frac{3}{4}\cdot\frac{3}{4}=\frac{9}{16} $$

[b]Case 2:[/b]
Both of $ad$ and $bc$ are odd.
For one of them to be odd, $a$ and $d$ are odd so the probability that $ad$ is odd is:
$$ \frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4} $$
Similarly $bc$ can be computed using the same method.
So:
$$ \frac{1}{4}\cdot\frac{1}{4}=\frac{1}{16} $$
Adding the fractions:
$$ \frac{9}{16}+\frac{1}{16}= \boxed{\frac{5}{8}} \ or \ \boxed{E} $$

===============================


Ο εγγεγραμμενος κυκλος ισοπλευρου τριγωνου $ ABC$ ξεκιναει να γινει περιγεγραμμενος διατηρωντας σταθερο το κεντρο του $ I$  .Κατα το μεγαλωμα του τεμνει κυκλικα τις πλευρες του στα  σημεια $ (K,L),(M,N),(O,P)$ (κινουμενα ανα δυο στην ιδια πλευρα). Να βρεθει το συνολο των προβολων του $ I$ στις $ LN,MO,NP,OK,PL,KM$

$ ($ Έχουν θεωρηθεί, τα σημεία $ K,\ L,$ με το $ K$ μεταξύ των$ B,\ L,$ πάνω στην $ BC,$ τα σημεία $ M,\ N,$ με το $ M$ μεταξύ των $ C,\ N,$ πάνω στην$ AC$ και τα σημεία $ O,\ P,$ με το $ O$ μεταξύ των$ A,\ P,$ πάνω στην $ AB$ $ ).$

Υ.Γ. Το Forum εχει εκπληκτικους γεωμετρες.Πολλοι προτεινουν ομορφες ασκησεις και καποιοι δινουν φανταστικες εως ψαρωτικες λυσεις . Μπραβο σας .Η παραπανω δεν διεκδικει τετοιες δαφνες.

δίνω σαν υπόδειξη ένα χρήσιμο Λήμμα.

[hide][b][size=100][color=DarkBlue]ΛΗΜΜΑ. - Επί των πλευρών $ AB \equal{} AC,$ ισοσκελούς τριγώνου $ \bigtriangleup ABC,$ λαμβάνουμε αντιστοίχως τα σημείa $ D,$ $ E$ $ ($ $ D,$ μεταξύ των $ A,$ $ B$ και $ C,$ μεταξύ των $ A,$ $ E$ $ ),$ έτσι ώστε να είναι $ BD \equal{} CE.$ Αποδείξτε ότι η πλευρά $ BC,$ διχοτομεί το ευθύγραμμο τμήμα $ DE$[/color][/size][/b].[/hide]

Κώστας Βήττας.

ΥΓ. Θα λείψω για δύο μέρες και δεν θα έχω επαφή με το φόρουμ. Την Τετάρτη, αν μέχρι τότε δεν έχει δοθεί συνέχεια στο πρόβλημα, θα βάλω σχήμα και περισσότερες λεπτομέρειες.

[hide]Το πρόβλημα αληθεύει για κάθε τρίγωνο, καθώς επίσης και όταν τα ζεύγη των σημείων τομής των πλευρών του, από τον κύκλο $ (I)$ καθώς μεγαλώνει η  ακτίνα του, δεν κείται μεταξύ των κορυφών του.

Δηλαδή το σύνολο των προβολών του $ I$ όπως ορίζει το πρόβλημα, είναι οι ευθείες των πλευρών του τριγώνου $ \bigtriangleup DEF,$ όπου $ D,\ E,\ F,$ τα σημεία επαφής του κύκλου $ (I),$ στις πλευρές $ BC,\ AC,\ AB,$ αντιστοίχως και αποδεικνύεται εύκολα ως άμεση εφαρμογή του Λήμματος που δόθηκε πιο πάνω.

Η απόδειξη του Λήμματος επίσης εύκολη, με βάση το [b][size=100]θεώρημα του Μενελάου[/size][/b].[/hide]

Κώστας Βήττας.

Ωραία προσέγγιση κ.Κώστα ... :)

Να μια διαφορετική .Θα δείξουμε για παράδειγμα ότι η προβολή του $ I$ στην $ OM$ ανήκει στην $ FE$ για το τυχαίο τρίγωνο $ ABC$ . Τα τρίγωνα $ OIF$ και $ EIM$ είναι ίσα άρα $ \angle{OIF} \equal{} \angle{EIM}$ επομένως $ \angle{OIM} \equal{} 180 \minus{} A$
άρα $ AOIM$ εγγράψιμο και από το θεώρημα Sιmpson οι προβολές του $ I$ στις $ AO,AM,OM$ είναι συνευθειακά σημεία επομένως η προβολή του $ I$ στην $ OM$ ανήκει στην $ FE$     :D

[quote="silouan"]Ωραία προσέγγιση Κώστα ... :)

Να μια διαφορετική .Θα δείξουμε για παράδειγμα ότι η προβολή του $ I$ στην $ OM$ ανήκει στην $ FE$ για το τυχαίο τρίγωνο $ ABC$ . Τα τρίγωνα $ OIF$ και $ EIM$ είναι ίσα άρα $ \angle{OIF} \equal{} \angle{EIM}$ επομένως $ \angle{OIM} \equal{} 180 \minus{} A$
άρα $ AOIM$ εγγράψιμο και από το θεώρημα Sιmpson οι προβολές του $ I$ στις $ AO,AM,OM$ είναι συνευθειακά σημεία επομένως η προβολή του $ I$ στην $ OM$ ανήκει στην $ FE$     :D[/quote]
Ωραία προσέγγιση Σιλουανέ και με το [b][size=100]θεώρημα Simpson[/size][/b], που μου ξέφυγε.

Ίσως το Λήμμα που ανέφερα, μας βοηθάει στο να δούμε ότι τα σημεία $ X,\ X',$ ( και ανάλογα τα σημεία $ Y,\ Y'$ και $ Z,\ Z'$ ) είναι πάντοτε συμμετρικά ως προς το μέσον του τμήματος $ EF.$

Κώστας Βήττας.

Επαληθεύονται τα λεγόμενα μου για καλούς γεωμέτρες


Let the set $S_n = \{1,2,3, \ldots,n\}$. A new multiplication $a * b$ is defined with the following properties:

(1) $c = a * b$ in $S_n$ for any $a \in S_n, b \in S_n,$
(2) if the ordinary product $a \cdot b$ is less or equal to $n$ then $a * b = a \cdot b,$
(3) the ordinary rules of multiplication hold for $*$, that is

(i) commutativity: $a * b = b * a$
(ii) associativity: $a * (b * c) = (a * b) *  c$
(iii) cancellation law: If $a * b = a * c$ then $b = c$.

Find a sutable multiplication table for the new product when $n = 11$ and $n = 12$.


algebra
polynomial
trigonometry
analytic geometry
superior algebra
superior algebra solved

Could anyone help to solve this question:

Find the minimal polynomial f in Q[x] for ζ = $\sqrt{2}*\cos(\frac{2\pi}{3})$Thank you very much!

eh... what about just $x^2-\frac{1}{2}$?

I got some hints from my prof today, but I'm still have problem to solve this question. Please help me.

f = $x^5 - 2$
Q($e^{\frac{2\pi i}{5}}$, $2^\frac{1}{5}$) = E
$e^\frac{2\pi ki}{5}*(2^\frac{m}{5})$ where $0 \leq k \leq 3$, $0 \leq m \leq 4$ span
and they are independent.

$(\sqrt{2})^k * e^\frac{2 \pi im}{3}$ where $0 \leq k \leq 1$ and $0 \leq m \leq 1$ where  $e^\frac{2 \pi i}{3}$ is a root of $x^2 + x + 1$

confused...

Let me explain Christian Hirsch's solution more carefully. Let $x=\sqrt{2}\text{ cos }\frac{2\pi}{3}=-\frac{\sqrt{2}}{2}$. This number is irrational, so the minimun polynomial of $x$ has degree at least 2. Therefore the question is that can we find a second degree polynomial with rational coefficients which has $x$ as a root? But we see that $x^2-\frac{1}{2}=\frac{2}{4}-\frac{1}{2}=0$ thus the minimum polynomial is $x^2-\frac{1}{2}$.

I don't see what you are doing in your solution. Is that some another problem?

Thank you Christian Hirsch and Puuhikki for your replies!

I'm learning the topic "roots of polynomials". Given ζ, to find its minimal polynomial is to find an irreducible polynomial f in F[x] such that f(ζ)=0, right?

What confused me is that my prof. gave us an example of finding such a polynomial for ζ = $\cos (\frac{2\pi}{5})$ and then the above question and asked us to solve it in the similar way.

His idea is ζ = $\cos(\frac{2\pi}{5}) = \frac{1}{2} * (e^\frac{2\pi i}{5}+e^\frac{-2\pi i}{5})$.  He discussed the polynomial $f = x^5 - 1$ and factored it into $(x-1)\Phi$ where $\Phi=(x^4+x^3+x^2+x+1)$. Then f(ζ) = 0 and ζ - 1 ≠ 0 → Φ(ζ )=0. Then the basis of Q[x]/f is 1, ζ , $\zeta ^2$, and $\zeta ^3$. Let η = 2ζ and find the coordinates of  η for this basis. Then he discussed the linearity of 1, η and $\eta^2$ and concluded that $\eta^2+\eta+1=0$. He said we could find the minimal polynomial of $x^5-2$ in this way. And today he gave us the hints for the above question.

I have no idea what he is doing...but every time I asked him, he confused me more...

That's why I come here for help. I hope someone understand his idea and can explain it to me. I will very appreciate for that!

I don't know what your professor is talking about. If $\zeta =\text{cos} \frac{2\pi}{5}$ then $\zeta^5-1\ne 0$.

Minimal polynomial can be defined as follows: Let $K$ be a field. A polynomial $f$ is the minimum polynomial of $\zeta$ over $K$ if it is of the form

\[ f(X)=X^n+\sum_{k=0}^{n-1}a_kX^k\in K[X]  \] such that $n\geq 1$, $f(\zeta)=0$, and $g(\zeta)\not =0$ for every $g\in K[X]$ as $1\leq\text{deg}(g)<\text{deg}(f)$.

It follows that the minimum polynomial of any $\zeta\in K$ is irreducible over $K$, but that is not taken as a part of the definition.

I think he is trying to show us a general way to find the minimal polynomial using the roots of unity. There may be some typos in his lectures. He gave us a complete example today:

Find the minimal polynomial in Q[x] for $\zeta = \cos\frac{4\pi}{9}$.
Solution: $\theta = e^\frac{4\pi i}{9}$ is a primitive root of 1. Therefore the minimal polynomial for $\theta$ is $\Phi_9 (x) = x^6+x^3+1$
The basis for $Q[\theta]$ is ${1, \theta, \theta^2, \theta^3, \theta^4,\theta^5}$. $\theta^6= - \theta^3-1$ and $\theta^9=1$.
Let $\zeta = \frac{\theta+\frac{1}{\theta}}{2}$ and let $\zeta_1=\theta+\theta^8$
Then $\zeta_1=\theta-\theta^5-\theta^2$
$\zeta_1^2=-\theta^4+\theta^2-\theta+2$
The coordinates for the basis:
$\zeta_1^0=(1,0,0,0,0,0)$
$\zeta_1^1=(0,1,-1,0,0,-1)$
$\zeta_1^2=(2,-1,1,0,-1,0)$
and these three are independent. then
$\zeta_1^3=\zeta_1*\zeta_1^2=(-1,3,-3,0,0,-3)$
Row acheloning of $\zeta_1^0, \zeta_1,\zeta_1^2,\zeta_1^3$ brings
$\zeta_1^0-3\zeta_1+\zeta_1^3=0$
substitute $\zeta_1=2\zeta$ obtain $8\zeta^3-6\zeta+1=0$ and then
the minimal polynomial $f(x)=x^3-\frac{3}{4}x+\frac{1}{8} \in Q[x]$

Anyone know this method? It's not from my textbook. It requires a lot of computations. Is there any better way to solve this kind of questions?


The points A(-3, 4), B(4,3), C(3,-4), D(3, 4), and E(-4,-3) are plotted on a rectangular plane. The line segment that is vertical is:

a. AD
b. BE
c. BC
d. CD
e. None of these

We are looking for the same x cordinate here...so the answer is [b][color=blue]D.[/color][/b] CD becuase (3,-4) and (3,4) have the x-coordinate kept the same.

The once with the same X coordinate is C and D, so the answer is D.


number theory
greatest common divisor
least common multiple
quadratics
inequalities
algebra

1) If the least common multiple of $ (10!)(18!)$ and $ (12!)(17!)$ is expressed in the form of $ a!b!/c!$, where $ a$ and $ b$ are two-digit numbers and $ c$ is a one-digit number, find $ abc$.

2) Given the sequence $ 10^{1/11}, 10^{2/11}, 10^{3/11},...,10^{n/11}$, what is the smallest value of $ n$ such that the product of the first $ n$ members of this sequence exceeds $ 100,000$?

3) If $ a$ and $ b$ are positive real numbers and each of the equations $ x^2 \plus{} ax \plus{} 2b \equal{} 0$ and $ x^2 \plus{} 2bx \plus{} a \equal{} 0$ has real roots, then find the smallest possible value of $ a \plus{} b$.

Thanks!

[hide="2."] Since $ 100000 \equal{} 10^5$, we are looking for the value of $ n$ such that the product of the first $ n$ terms in the sequence is greater than $ 10^{\frac {55}{11}}$.

One less than such an $ n$ is given by the equation $ \frac {(x \plus{} 1)(x)}{2} \equal{} 55$. Disregarding the negative solution, we have $ x \equal{} 10$. Therefore our final answer is $ n \equal{} 11$.[/hide]

[hide="number 1"]Let $ 18!$ equal $ a$ and $ 12!$ equal $ b$. We wish to find the least common multiple of $ \frac {ab}{18}$ and $ \frac {ab}{132}$ The gcd of 18 and 132 is 6 so the lcm of $ \frac {ab}{18}$ and $ \frac {ab}{132}$ is $ \frac {ab}{6}$ which equals $ \frac {18!12!}{3!}$. $ 18\times{12}\times{3} \equal{} \boxed{648}$.[/hide]

[hide="3"]For a quadratic equation to have real solutions, the Discriminants must be non-negative.

So we have these inequalities:
$ a\leq{b^2}$
$ a^2\geq{8b}$

First we try $ b\equal{}1$. Then $ a$ must also equal 1 to satisfy the first inequality. But if $ a$ equals 1, the second inequality is false. Now try $ b\equal{}2$. $ a$ then can equal 1,2,3, or 4 to satisfy the first inequality. But the only value of $ a$ that also satisfies the second inequality is $ a\equal{}4$ so the answer is $ 2\plus{}4\equal{}\boxed{6}$[/hide]

In tinytim's solution for number 1, I don't get why we are looking for the least common multiple of $ \frac{ab]}{18}$ and $ \frac{ab}{132}$.

[quote="Illos"][hide="2."] Since $ 100000 = 10^5$, we are looking for the value of $ n$ such that the product of the first $ n$ terms in the sequence is greater than $ 10^{\frac {55}{11}}$.

One less than such an $ n$ is given by the equation $ \frac {(x + 1)(x)}{2} = 55$. Disregarding the negative solution, we have $ x = 10$. Therefore our final answer is $ n = 11$.[/hide][/quote]

For this solution, $ 10^{\frac {55}{11}}$ equals $ 100,000$.  How do we know that we must go up until $ 10^{\frac {55}{11}}$?  Couldn't some of the previous terms sum up to $ 100,000$?

Thanks a lot!

[hide="1"]The least common multiple of two numbers is defined as
\[ LCM(a,b) \equal{} \dfrac{ab}{GCD(a,b)}
\]
,
so we must find the GCD of those two numbers. We can divide out $ (10!)(17!)$ from both sides to get $ 18$ and $ 132$, and the GCD of those two numbers is 6. So $ GCD((10!)(18)!,(12!)(17!)) \equal{} 6(10!)(17!)$. Thus $ LCM(a,b) \equal{} \dfrac{(10!)(12!)(17!)(18!)}{6(10!)(17!)} \equal{} \dfrac{(12!)(18!)}{3!}$. $ 12*18*3 \equal{} \boxed{648}$[/hide]

[hide="2"]We take the product of the first $ n$ terms and we get 10 to the $ \dfrac{n(n \plus{} 1)}{22}$th power, and $ \dfrac{n(n \plus{} 1)}{22}>5$. Thus $ n(n \plus{} 1) \minus{} 110>0$. Obviously $ 10(10 \plus{} 1) \equal{} 110$, so the next highest one, $ \boxed{11}$ should satisfy it.[/hide]

@314.math: He's saying that the sum has to go up to 55/11, then over it. If we stop before 55/11, we won't go over it.

[quote="tinytim"][hide="number 1"]Let $ 18!$ equal $ a$ and $ 12!$ equal $ b$. We wish to find the least common multiple of $ \frac {ab}{18}$ and $ \frac {ab}{132}$ The gcd of 18 and 132 is 6 so the lcm of $ \frac {ab}{18}$ and $ \frac {ab}{132}$ is $ \frac {ab}{6}$ which equals $ \frac {18!12!}{3!}$. $ 18\times{12}\times{3} \equal{} \boxed{648}$.[/hide]

[hide="3"]For a quadratic equation to have real solutions, the Discriminants must be non-negative.

So we have these inequalities:
$ a\leq{b^2}$
$ a^2\geq{8b}$

First we try $ b \equal{} 1$. Then $ a$ must also equal 1 to satisfy the first inequality. But if $ a$ equals 1, the second inequality is false. Now try $ b \equal{} 2$. $ a$ then can equal 1,2,3, or 4 to satisfy the first inequality. But the only value of $ a$ that also satisfies the second inequality is $ a \equal{} 4$ so the answer is $ 2 \plus{} 4 \equal{} \boxed{6}$[/hide][/quote]

I don't get the solution for the third problem.  How were the following inequalities gotten?

$ a\leq{b^2}$
$ a^2\geq{8b}$

Thanks!

the discriminant of of a quadratic equation $ ax^2\plus{}bx\plus{}c\equal{}0$ is $ b^2\minus{}4ac$. If it is greater than 0, then the equation has 2 different real solutions. If it equals 0, then it has 1 repeated real solution. If it is negative, then it has 2 different unreal solutions.