Bharat Rakshak

Posted: **18 Aug 2008 22:34**

AmberG is la pata after that post?

Host cant quit without notice. See first post of this thread.

Posted: **18 Aug 2008 23:07**

Wiki wrote: Any two closed curves in space can be moved into exactly one of the following standard positions. This determines the linking number.
Each curve may pass through itself during this motion, but the two curves must remain separated throughout.

Not noticing the bolded part could lead to confusion

.

Posted: **18 Aug 2008 23:20**

A number of men and women stand in a line holding hands. There are an unspecified number of men and women, the only condition being that the there is a woman at the beginning of the line and a man at the end. If two members of the opposite sex hold hands, they are obliged to have a baby

. Show that there will be an odd number of babies.

Posted: **19 Aug 2008 01:05**

SK Mody wrote:A number of men and women stand in a line holding hands. There are an unspecified number of men and women, the only condition being that the there is a woman at the beginning of the line and a man at the end. If two members of the opposite sex hold hands, they are obliged to have a baby . Show that there will be an odd number of babies.

Seems too low-funda for this thread.
Start tracking gender starting from one end of the thread.
Gender changes each time there is a baby and an odd number of gender changes are needed for the other end to be of opposite gender.

Posted: **19 Aug 2008 02:29**

I will try to explain the notion of winding number. The notion of winding number occurs in many
places. It occurs in the theory of liquid crystals, and what mathematicians call harmonic maps.
Special cases of harmonic map theory is liquid crystals. It occurs in the study of vortices in
superfluids like liquid Helium, as part of a theory first developed by the Russian Nobel laureates
Ginzburg and Landau. In more sophisticated forms it occurs in Yang-Mills theories in the form
of Chern classes, topological charges and other things. S.S.Chern being the famous Chinese-American mathematician who was the thesis advisor of the Fields medallist ST Yau. More importantly the winding number
in its most elemental form appears on the top of everyone's head in the form of whorls. Notice
no human being alive has a head of hair without whorls unless bald.
There is a famous theorem that states that on a two-dimensional sphere there CANNOT be a field
that is tangent to every point on the sphere unless the field vanishes at SOME point.

Think of the head as the sphere, the hair pretend it to be the field lines and assume each field line is tangent to the head then the whorl is where the field vanishes. Notice the condition of tangency is very important, for if not you can always imagine the situation the hair standing straight up like a hairy ball and no whorl. So you see when you read a theorem it becomes very important to read the conditions very, very carefully.

Now let me give a naive notion of the winding number. First the winding number is associated to two things
you need a MAP and you need a POINT in the IMAGE of the map. Notice for linking number you need closed loops no maps and no points!!.
So already the difference has manifested itself. OK so lets take a very simple example. Take the map
in the complex plane w=f(z)=z^2. Now take a point in the image w=0. I want to define the winding
number H(f,w=0). How do I do it? There are other ways of doing it but those ways will hide the "winding part"
of the idea so I choose this way. The winding number is the way the function is winding itself around a point so to say.
So for our choice w=0 look at the pre-images, we find only one z=0.

Take a circle or any loop(it needs a lemma that it does not matter what curve you take) around z=0.
Look at the image of this loop in the w-plane. Now walk say counterclockwise around the loop in the z-plane.
How many times have you walked around the loop in the w-plane. Answer=2 times COUNTERCLOCKWISE. So the winding
number=H(f,0)=2. Now change the situation a little bit. Take w=g(z)=(bar z)^2, where bar z is the complex conjugate.
Do the same construction. Now as you travel counterclockwise in the z-plane you will now travel CLOCKWISE twice
in the w plane so the winding number H(g,0)=-2.

Now take w=1. Take w=z^2 again. Then the pre-images are z=1 and z=-1. Now take little circles around each point z=1 and z=-1
and see what happens as you walk around once counterclockwise in the z plane. You will find that it will be once counterclockwise in the w plane for both circles around z=1 and z=-1. The winding number is then the SUM
of the winding numbers you get from z=1 and z=-1 and hence H(f,w=1)=2. So one adds the winding numbers
from each local contribution for each and every pre-image.

The winding number is a powerful tool to prove the theorem above. It is also a powerful tool that can be used to prove the Brouwer fixed point theorem. This theorem states that if f is continuous map from
a convex set(think of a ball) to the same convex set then there is a point x for which f(x)=x the so-called fixed point. Once the standard properties of winding number is established it is easy to prove this result. Popular math. books state it as:

Take some coffee in a coffee mug( a convex set). Stir it ( a continuous operation). let it come to rest, we performed a map of the set to itself. Then at least one point of the coffee did not move.
There are infinite dimensional versions of this theorem and the notion of the winding number that is also
called the topological degree. This infinite dimensional notion is called the Leray-Schauder degree. Schauder discovered this notion while teaching in a high school in Poland. During WW2 he was caught by the Nazis because he was a Jew and horribly tortured in a shameful medical experiment. Leray a Frenchman was interned during WW2 and did superlative work even while in prison. His theorem on the Navier-Stokes equation remains unsurpassed though there lots of people make noise.

The winding number or degree appears in the theory of soap bubbles and it is here I have used it to examine
bubbles of winding number =1. Sort of corresponding to f(z)=z. The higher winding number situation was too hard for my collaborator and me to handle and eventhough we have lots of notes and calculations there is no definitive result. Here is what we did.

Soap Bubbles

Look at eqn 7 that is the formula for the map. Its winding number is 1.

Posted: **19 Aug 2008 10:19**

vsunder wrote:Take a circle or any loop(it needs a lemma that it does not matter what curve you take) around z=0.

Hmm.. Is that because it is a derivative of a potential function and not path dependent and hence the line integral around any random closed loop is the same as that of a circle kind of thing like you would use to prove Green's theorem ? After all, if the complex function is differentiable, it is infinitely differentiable arent' they?

Look at the image of this loop in the w-plane. Now walk say counterclockwise around the loop in the z-plane.
How many times have you walked around the loop in the w-plane. Answer=2 times COUNTERCLOCKWISE. So the winding
number=H(f,0)=2. Now change the situation a little bit. Take w=g(z)=(bar z)^2, where bar z is the complex conjugate.
Do the same construction. Now as you travel counterclockwise in the z-plane you will now travel CLOCKWISE twice
in the w plane so the winding number H(g,0)=-2.

Saar. Question here. If I remember my complex analysis from close to a decade and a half ago, one of the transformation under conformal mapping of z^2 is a straight line isn't it? (not sure..maybe it was a different function , but a circle transforms to a straight line is one I remember from the depths hidden away somewhere under layers of grime and disuse), so, if in such a transform you go around either clock wise or anti clockwise in a circle in the z plane, in the w plane (the mapped plane), since you come back to the starting point (I guess in the transformed plane, you would go up and come back down to the starting point right?) , so if as you state below that the winding numbers are additive

Now take w=1. Take w=z^2 again. Then the pre-images are z=1 and z=-1. Now take little circles around each point z=1 and z=-1
and see what happens as you walk around once counterclockwise in the z plane. You will find that it will be once counterclockwise in the w plane for both circles around z=1 and z=-1. The winding number is then the SUM
of the winding numbers you get from z=1 and z=-1 and hence H(f,w=1)=2. So one adds the winding numbers
from each local contribution for each and every pre-image.

So wouldn't the winding number in that case be zero ?

Posted: **19 Aug 2008 11:42**

Vina: I think you are making a completely elementary thing complicated. What I have said is totally elementary.
The fact of the matter is winding number has nothing to do with conformality, or complex analysis or whatever.
The notion makes complete sense for a continuous function. Remember I am hammering away repeatedly in my post that it is a topological concept. In any case what good is complex analysis in 3 dimensions where winding number or degree still makes sense but complex analysis has no meaning. I just brought in complex analysis simply because it is easy to write a formula for f using complex notation or else I would have to write for w=f=z^2.

f:(x,y)------> ( x^2-y^2, 2xy) --------(1)

What a horrible way to write something!! If you wish you can use the notation (1). I find it easier to use
the formula w=z^2.
In the case of w=z^2. Take a circle around z=0. The circle can be parametrized as z=exp(it) with 0<t<2 pi
or as (cos t, sin t) if you prefer. Now what is w(t)=z^2 it is w=exp(2it). This is the image curve. If you wish you can write this as w(t)=( cos 2t, sin 2t). Now note you will go around twice in the image curve. Maybe I am misreading what you write. If you use the formula (1) you will get for x=cos t, y=sin t

(cos^2 t-sin^2 t, 2 sin t cos t). Since all of you think passing JEE is some sort of mathematical greatness
then you will tell me that every JEE topper knows immediately that cos 2t= cos^2 t-sin ^2 t, 2 sin t cos t=sin 2t.
and so w(t)=(cos 2t, sin 2t). But I prefer using complex analysis to do the trivial calculation.

Posted: **19 Aug 2008 12:35**

vsunder wrote: I just brought in complex analysis simply because it is easy to write a formula for f using complex notation or else I would have to write for w=f=z^2.

f:(x,y)------> ( x^2-y^2, 2xy) --------(1)

What a horrible way to write something!! If you wish you can use the notation (1). I find it easier to use
the formula w=z^2.
In the case of w=z^2. Take a circle around z=0. The circle can be parametrized as z=exp(it) with 0<t<2 pi
or as (cos t, sin t) if you prefer. Now what is w(t)=z^2 it is w=exp(2it). This is the image curve. If you wish you can write this as w(t)=( cos 2t, sin 2t). Now note you will go around twice in the image curve. Maybe I am misreading what you write. If you use the formula (1) you will get for x=cos t, y=sin t

Ah. Thanks, now I understand where you are coming from. I got thrown when you started using "maps" and brought in complex analysis notation and I immediately jumped to conformal mapping and Jacobian and all that transformation rubbish.

What you are saying in effect in that if you consider a unit circle (not necessarily, will scale fine even if some r) and apply the transformation w = z^2, you basically are blowing up to twice the dimension in all effects (area, length, speed , angular displacement etc).. So, if you were walking at a speed of omega in the first dimension, you would walk at twice omega in the w= z^2 map and cover two circles in the while you covered one circle in the z plane .. (correct me if I am wrong). That is the plain English and intuition behind all the math I think.

(cos^2 t-sin^2 t, 2 sin t cos t). Since all of you think passing JEE is some sort of mathematical greatness
then you will tell me that every JEE topper knows immediately that cos 2t= cos^2 t-sin ^2 t, 2 sin t cos t=sin 2t.
and so w(t)=(cos 2t, sin 2t). But I prefer using complex analysis to do the trivial calculation.

Us JEE types also know Euler's formula and that e^it = sin(t) + i cos (t) and and that (e^it)^2 = sin(2t) + i cos(2t)!.. So we would have got that subtending twice the angle from w= e^it itself without all that trigonometry!

But that apart, lets talk about the transformation I mentioned , ie transformation of a circle to a straight line. Lets look at concrete every day instance where it happens. The transformation of a rotary motion to linear motion like it happens in a pump or , vice versa, where the linear motions of a piston in an engine is transformed to the rotary motion of a crank in an engine (well not exactly linear and rotational, but with a sufficiently ..heck, you are a math guy so lets dispense with engineering rubbish , infinitely long connecting rod , it will be transformed from linear to rotational and vice versa)..

For every rotation of the crank (ie 360 degree rotation), the piston comes back to it's starting point. So you will do one rotation. I can understand how the area subtended by the rotation of the crank disc will be directly related to the area swept by the piston ( determinant of Jacobian times swept area if I am correct?) .Yeah, that will be the linking number you in this case (like the 2 in the z^2 transform you used to illustrate) and it will be additive. So while the areas will be additive, how does that translate into additives of displacement. I am a bit confused on that part and that was the question I asked you about..(I would snivel and say the net displacement of both the piston and crank are zero after each cycle ,but somehow think that might not be the right answer)..So would appreciate if you have any thoughts on that.

Posted: **19 Aug 2008 20:09**

Nandu wrote:
SK Mody wrote:A number of men and women stand in a line holding hands. There are an unspecified number of men and women, the only condition being that the there is a woman at the beginning of the line and a man at the end. If two members of the opposite sex hold hands, they are obliged to have a baby . Show that there will be an odd number of babies.
Seems too low-funda for this thread.
Start tracking gender starting from one end of the thread.
Gender changes each time there is a baby and an odd number of gender changes are needed for the other end to be of opposite gender.

Neat. In that case try this one.
You are given a triangle ABC. Call this triangle the main triangle M. This M is further subdivided into a finite number of sub-triangles in such a way that every side of every interior sub-triangle is common to exactly two triangles (a side of a triangle is defined as the line between two adjacent vertexes). The sides that lie on the boundary of ABC are of course not shared. Now each vertex of each sub-triangle is given any one of the labels A, B or C at whim with the condition that vertices on the side AB of M are only given A or B labels, vertices on the side AC of M are given only A or C labels and vertices on the side BC of M are given only B or C labels.

A sub-triangle is called complete if it has labels ABC.

Show that there are an odd number of complete sub-triangles.

(Note: Sub-triangle means "elementary" sub-triangles, that is there are no other triangles inside the sub-triangle).
(Note2: If you have seen this before - apologies)

Posted: **19 Aug 2008 22:10**

Vinaji,
I am sure you meant exp(it)=cos t + i sin t and not sin t + i cost t as every JEE person can vouchsafe! (and quite a few non JEE folks too....

).

Posted: **20 Aug 2008 08:58**

Neat. In that case try this one.
You are given a triangle ABC. Call this triangle the main triangle M. This M is further subdivided into a finite number of sub-triangles in such a way that every side of every interior sub-triangle is common to exactly two triangles (a side of a triangle is defined as the line between two adjacent vertexes). The sides that lie on the boundary of ABC are of course not shared. Now each vertex of each sub-triangle is given any one of the labels A, B or C at whim with the condition that vertices on the side AB of M are only given A or B labels, vertices on the side AC of M are given only A or C labels and vertices on the side BC of M are given only B or C labels.

A sub-triangle is called complete if it has labels ABC.

Show that there are an odd number of complete sub-triangles.

(Note: Sub-triangle means "elementary" sub-triangles, that is there are no other triangles inside the sub-triangle).
(Note2: If you have seen this before - apologies)

The only way a vertex of a sub-triangle will have a label at all is if it lies on one of the original edges AB, BC, CA.

If we accept the above then there are only 2 cases as outlined in the diagram above.
Case 1 : WLOG assume that one of the vertices is A and the other vertices of the sub-triangle are on the opposite site BC. If that be so and if the scheme to number the vertices are as specified in the question then there can only be an odd number of such triangles. Reasoning is similar to the answer for your previous question. From A to B, with intermediate vertices numbered A or B there has to be an odd number of transitions. QED

Case 2 : The other subtriangles are of the type drawn in Case 2 in the diagram. In that case there are only 6 ways of assigning A,B or C to the vertices of the subtriangle. I have drawn the case for 2 of them only. The others are symmetrical to the case. In 2A, there is only 1 sub-triangle which is complete. In 2B also there is only 1 sub-triangle which is complete. QED

Posted: **20 Aug 2008 10:17**

Najunamar wrote:Vinaji,
I am sure you meant exp(it)=cos t + i sin t and not sin t + i cost t as every JEE person can vouchsafe! (and quite a few non JEE folks too.... ).

.

Thanks for the correction. Just shows you to the depths you sink to if all you do is financial models on spread sheets and some statistical modeling and regression analysis and auto regressive models for time series analysis!

Posted: **20 Aug 2008 20:39**

sugriva wrote:
The only way a vertex of a sub-triangle will have a label at all is if it lies on one of the original edges AB, BC, CA.

This need not be the case. There can be any number of interior triangles.
See this picture

Posted: **21 Aug 2008 04:26**

AmberG is la pata after that post?

Host cant quit without notice. See first post of this thread.

Sorry, I have been out for a while. Let me just touch a few points which I think are necessary.

AmberG, Vsunder is respected mathematician. his work was appreciated by the greats like S Chandrasekhar himself. I understand your strong point is physics. If one didn't understand the problem one can ask for clarification. No need to consider it humorous etc. I am sure you didnt mean to insult. So please edit your posts. Thanks, ramana

Vsunder, please don't go off. We do need you. Ramana

Ramana – I have re-read my post, and honestly do not find that I was insulting anyone. The problem made no sense to me as it was not clear(to me at least), and I in fact asked specific questions about the ambiguity (you get c=3 for n=1 and c=2 for n=2), and asked it to be explained. There was no personal attack, only asking if problem can be made unambiguous.

I have asked similar questions to famous/great people if there was ambiguity – (Like S. Chandrasekhar, F. Dyson – taken from your list) and none has ever taken offense.

BTW, did id you check the reference(s), Vsunder gave? That do not clarify the problem (at least to me). If so can you explain/simplify/quote the problems/ In fact one link given by Vsunder gives the following error:

Code: Select all

<DPubS-Response version="1.0">
<responseDate>2008-8-20T17:20:13Z</responseDate>
<request>not specified</request>
−
<error>
The server was unable to service your request.
because of the following error:
Unsupported or malformed request
</error>
</DPubS-Response>
(this is after:

The lemma 2 that makes no sense appears here. If you feel it does not make sense write to the editorial board.

Another link which tells Here is one which eventually appeared in the American Journal of Mathematics one of the leading journals of the world in 2004. points to
“Sign and area in nodal geometry of Laplace eigenfunctions
Authors: Fedor Nazarov, Leonid Polterovich, Mikhail Sodin
Which was published in American Journal Math. 127 (2005), 879-910

Again I do not know how Laplace eigenfunctons are related to the problem in hand. May be it is my ignorance, but can you (Ramana, Vsunder or other posters) make it easy so that I can understand.

Again, no disrespect meant, but can you clarify (or just quote from those links – just cut and paste the wordings in the paper which are similar to the problems posted) the problem. I can see no connection, but am willing if some one can put it here in simplified terms. ...

Also , where I went wrong when I was taking a particular case, and found C=2 (for n=2 case?)

In short, all I asked to clarify the problem, would be glad if the problem is clarified.
To me, at least, the problem still makes no sense, perhaps some one can clarify. I had NO intention of insulting anyone so would like to see actual math part here.

I finally don’t know what to make out of

Amber you need to be polite to people, you are very arrogant and have no mathematical research to your credit.

Vsunder does not know me, how does he know that I have no mathematical research to my credit? Isn’t that rather rude and arrogant? (and inaccurate, to put it mildly).

Posted: **21 Aug 2008 04:29**

shiv wrote:
vsunder wrote: Forum admins: I must say the forum has degenerated into a cesspool of name calling arrogance by petty foggers
and sundry others. I have decided to stop coming here. It was nice in the old days and I am happy I learnt many things from people.

Sagun
Sagun, I admit that the post by AmberG (quoted below) was unnecessarily aggressive and egotistic. Since I know you personally I would like to apologize for this idiocy. Postor AmberG has not spared even a few microseconds to think that anyone else might know any math, which is sad for a person who wanted to test the math ability of forum members on the nuclear discussion thread a few weeks ago.

Amber G. wrote: It's not April 1, but I will bite. If this is not a joke, could one please write it in a way so it makes sense mathematically by being precise in definition.
For example: What exactly the sentence mean "Take a square it works for a cube in any dimension." ?? If rest of the part is particular example in D2, then state so, if not, then were exactly, say 4 in 4^n comes from?
Also what is "N" is is different than "n"? for example, when n=1, we have only one choice (3 squares) making C=3 (Assuming N and n are same) while for n=2, one can easily get an example where you need only 2 squares to cover.

In short it makes no sense.

If this was a joke, can the spam be removed.

(I am not even commenting on the rest of the post.. as it makes even less sense to me)
Thanks in advance.

Shivji- I have warning in my in box, and can not reply as PM hence the message is here.

This was uncalled for:

Postor AmberG has not spared even a few microseconds to think that anyone else might know any math, which is sad for a person who wanted to test the math ability of forum members on the nuclear discussion thread a few weeks ago.

Asking if n is same as N, or asking clarify the problem, or asking if the problem is a serious one ,

Or asking some one to clarify because the link which he posted gives the result like:

<error>
The server was unable to service your request.
because of the following error:
Unsupported or malformed request
</error>
</DPubS-Response>

IMO, does not require that rebuke.

To put it mildly there is no truth in that I will not “spared even a few microseconds to think that anyone else might know any math”.

On one hand you let it go comments like:

Amber you need to be polite to people, you are very arrogant and have no mathematical research to your credit.

(How do you or the postor know if I have “no mathematical research to my credit?”

I think that is a double standard.

Regards.

Posted: **21 Aug 2008 10:37**

So I did something really cute for you guys. Remember I was talking about the whorls on the head
and winding number. First that theorem that on the two dimensional sphere any field that is tangent has to vanish
at some point, that theorem is called the Hedgehog theorem and you can look it up.
Now the cute part. I wrote a little program on MAPLE and made MAPLE fieldplot w=z^2
or in the real version

f: (x,y)------> (x^2-y^2, 2xy)

The plot or field lines shows the whorl at the origin and more importantly the degree 2, or winding number=2
character of f is seen very clearly. I loaded the file and plot to my web page, check it it is really cute. Here is the link:

Maple plot of f

Posted: **21 Aug 2008 23:39**

From a non-mathematical fly on the wall - here are my two worthless zimbabwaen cents

Both AmberG and vsunder are quick on the gun to take offence.

From AmberG

It's not April 1, but I will bite.
If this is not a joke
In short it makes no sense.
If this was a joke, can the spam be removed.
(I am not even commenting on the rest of the post.. as it makes even less sense to me)

One statement was probably okay, but piling on five at a time is just enough to press vsunders buttons. So yes amberg, maybe you need to rephrase your statements better, think twice and see the posiblity that the other person is serious and not joking/being silly/spamming the board.

From Vsunder:

Amber you need to be polite to people

OK

, you are very arrogant

Sort of OK again in light of over criticism by Amber

have no mathematical research to your credit.

here he loses it - how does vsunder know who what AmberG does for a living?

I have decided to stop coming here

The above seems to be a favorite refrain of anyone who cant take heat.

I actually heard a similar statement when a previous member took offense elsewhere - I think that was amberG on the nuke thread

So both of you professors need to chill out. have a beer and get back into this thread.

Posted: **22 Aug 2008 19:14**

To paraphrase Twain. It is easy to stop coming here. I've done it dozens of times.

Posted: **25 Aug 2008 09:51**

Hari C –

Thanks for comments and I will try to answer/comment you honestly (as honestly as I can)

I NEVER intended to insult or take offense in ANY way to Vsunder.
Obviously you are not the only one (there are two Bradmin and warning – not to mention quite a few other posters here who took offence on what you quoted) so it may be hard for some to believe, but honestly my comments were about the problem he posted (not about him) and the references which he posted which made no sense (at least to me) and still makes no sense (to me). And, I still see no one has taken time to make those points clear which can show such that the problem is indeed serious and where I am wrong in misunderstanding it.

FWIW, In academic environment I am used to, the comments which I made (“your problem make no sense - (no reference to “you”) will not make other math professional take offence.

One thing when we ask math problems is to make that precise, and if there is some ambiguity in wordings which the other person does not understand (even if it is other person’s fault) one tries to make the problem clear. So if you (or any one else has) understood the problem I would be grateful if you can explain it. (In previous message, I do have asked what I found to be ambiguous)

Please note:

The references/links he gives (I encourage others to check them out) does not clarify the problem(s). As I said in previous post, one link gives error, and other, at least for me, bears little connection with the original problem. If you find the connection, please let me know. I apologize in advance if this sound rude, but if possible, show how those links are related or makes the original problem clear.

To make it more confusing, posts telling me the work of V sunder, points to different people (Multatuli’s post points to different person than Shivji’s post)

In any case, I am still interested, if some one can post the problem in clearer form.

Posted: **25 Aug 2008 10:44**

Look up
http://www.vedicbooks.net

and search for author kenneth williams

And

Vedic Math Teachers Manual, 3 volumes
Elementary, Intermediate, Advanced, $10 each

This has single step multiplication, division for very large numbers
many of them mentally solved

Mentally solving 2 digit multiplication, square roots, cube roots

Divisibility of numbers,
Trignometry,
and much much more

Posted: **27 Aug 2008 03:07**

OK, can we get back to the puzzles?

AFAICS, the two unsolved problems are the Ankan one from Amber G. and the triangle division one from SK Mody, yes?

I am not getting very far with either of those.

Posted: **27 Aug 2008 07:28**

This is not exactly a math question but I did not know any better place than this thread to ask this question. So, admins please forgive my transgression.

You have an array of n integers, randomly ordered, each with a value between 1 and (n-1). The array is such that there is one and only one value that occurs twice. Write a function that returns the repeated value. You may not call any .NET Frameworks functions. I would prefer the function written in C# but pseudo code would do as well. Thanks!

Sample input: [4 1 3 2 1]
Correct sample output: 1

Posted: **27 Aug 2008 08:59**

Karan, no offense intended, but I think it behooves you to let us know where the problem comes from.

As for posing CS questions, algorithms are related to Math in a sense, and if physics problems can be discussed here, so can algorithms. IMHO, of course.

I presume you are looking for something better than the obvious n*(n-2)/2 comparisons approach?

Is the algorithm allowed to reorder the array? And if so will a sort followed by (or modified to do) comparisons
of consecutive elements do? That would be O(N ln N).

Posted: **27 Aug 2008 09:50**

Nandu,

A friend of mine needs to solve this as part of his job interview (technical screening).

The array is randomly ordered and does not follow any specific sort order.

Posted: **27 Aug 2008 10:55**

I really shouldn't help candidates with job interviews, but there's a really easy way to do it without sorting anything. Only took me one minute to figure it out and comes out to a one liner in python or ruby. The first two methods I thought of are less efficient, but will work as well.

With all due respect, if your friend couldn't come up with one of these solutions yet, maybe he or she is in the wrong business IMHO. Just my two cents.

Posted: **27 Aug 2008 17:53**

K Dixit no need of sort

x= sum(array)-n(n-1)/2

Posted: **27 Aug 2008 21:27**

karan This thread is for recreation and to brush up on maths. Its not to help folks get unfair advantage. Thats unethical. it look sto you like givng you rfriend some help but its more like nepotism. And Indians have been accused of that please dont do it again. Thanks, ramana

Posted: **27 Aug 2008 21:28**

AFAICS, the two unsolved problems are the Ankan one from Amber G. and the triangle division one from SK Mody, yes?

Nandu - Big hint is SK mody's first problem, Take line A B Call A man, B woman then the number of 'AB' type pairs (change in parity) on line AB has to be odd.
Rest is easy
Remove all internal borders which are connect with line AB.
Now count all the lines of the type AB. this has to be odd.
(A complete triangle has only 1 AB type line - others have either 0 or 2 AB type line), since number of AB type lines are odd (after removing all internal AB borders) we must have at least 1 (and odd) number of complete triangles.

This is particular case of Sperner's lemma (Check wikipedia or wolfram or other internet resources) for n=2.

Sorry if the solution was already posted.

{Edited ramana}

Posted: **27 Aug 2008 23:33**

Sorry, can no longer edit the old post (admin's if you can do it, please do it)
I meant wolfram (http://mathworld.wolfram.com which is a very good resource for math related subjects.
I had a typo it is NOT "wolfman"

but wolfram).

Added later: In the original problem you can also prove, that the number of "clockwise" triangles are exactly one less or more than "counter clockwise" triangles. (With obvious/natural interpret ion of "clockwise"
(this can be little harder but not really that harder)

(Also, not very explicitly mentioned in earlier post - any internal 'AB' type border removal will not effect evenness/oddness, since any internal line will effect 2 triangles - which borders it)

Posted: **27 Aug 2008 23:35**

Ramana,

You are jumping the gun. He is allowed to seek help. As long as he can explain the answer in the final interview. He got thick booklet filled with questions. That was just one of the questions. Poor kid. Nothing unethical there except in your mind.

ArmenT,

I do not know about Ruby or Python. However, it is easy to do it in C# using .Net Framework function. But he is not allowed to use the .Net Framework functions. Were you able to do it in one minute without using .Net Framework functions?

Vriksh,

Thanks! Your solution seems to be the correct one. The poor kid will thank you.

Posted: **28 Aug 2008 00:08**

Oops I didn't realize the array size was conveniently set.

Yes, it is a rather simple maths problem.

However, I am with Ramana on the ethics of the situation.

Posted: **28 Aug 2008 00:14**

Rumor is that a new "largest known prime" (mersenne prime number) number is found.. wait for a few days (about 2 weeks will be needed for it to be rechecked) till it gets checked out, and if so verified , it might hit the news.. Last largest know prime number discovered in 2006 was 2^32582,657 -1.
(I think $100,000 prize is going to be claimed - if the number checks out)
(It may be interesting that the story is being breaking out in BRF many days ahead of main news stream media - that is if the number gets independently verified to be a prime)

Posted: **28 Aug 2008 03:40**

Amber G, here is my solution to your ankan problem (actually a slightly stronger result):

I will show that given any p, there is a multiple of p that has only 0's and 1's.
Let p be any number. The remainder when 10^k (k = 0, 1, 2, ... etc ) is divided by p is some number between 0 and p-1 inclusive.
Consider:
case 1: 10^k is divisible by p for some k. In that case there is nothing to prove.
case 2: There is no value of k for which 10^k is divisible by p. In this case, consider the remainders r0, r1, r2, r3, ... defined by:
10^0 = p*q0 + r0
10^1 = p*q1 + r1
10^2 = p*q2 + r2
... and so on, ad infinitum.
Since there are only a finite number of possible remainders, it follows that at least one of the remainders must occur an infinite number of times. Call this remainder r. Then we have:
10^k1 = p*s1 + r
10^k2 = p*s2 + r
10^k3 = p*s3 + r
... for some infinite sequence of k1 < k2 < k3 .....

Now go all the way up to kp. (ie: k1, k2, k3, ... k_p) and add the above equations. We get:
10^k1 + 10^k2 + 10^k3 + .... + 10^k_p = p*(s1+s2+s3+ ... s_p) + pr

The right hand side is a multiple of p. The left hand side is a sum of different powers of 10 - so its digits contain only 0's and 1's.

This is not of course the smallest number with the required property. That would be another question.

I think this problem was somewhat more difficult (as a problem solving exercise) than the cow/buffalo one, but you seem to think otherwise.

Posted: **28 Aug 2008 04:09**

Amber G. wrote:Rumor is that a new "largest known prime" (mersenne prime number) number is found..

It would be interesting to know if this has any implications for cryptography.

Posted: **28 Aug 2008 04:54**

SKM - Neat!

(You can, perhaps simplify it a little, just take two numbers with the same 'r' - as you proceeded to do, and subtract. the closest two .. that you will get 999... followed by 0's - the number(difference) would obviously be a multiple of n since two numbers (10^k, 10^l gives the same remainder when divided by n)

For others, this is same principle as SKM's but the following may be, perhaps a little easier: The method is called 'kabootar kabootar' (also known as Dirichlet's or pigeon hole theorem).

Basically it says if there are n 'kabootars' and m
kabootar pinjras' and if n>m (and every kabootar is in a pinjra) then there is atleast one pinra which has more than one kabootar!

(Not going to hide the solution, as the problem has been here for a long time.)

to refresh the ankan problem (modified more strongly per Mody) is now

given any number n , there is a multiple of n which can be written as 11111...000...
the above obviously as ankan =2 (you add 0's if ankan =1 and you want to make it 2 )

One possible Solution:

Code: Select all

You get [b]n [/b] pinjra (or pigen-holes) number 0,1,2,3, ... (n-1)
Now get kabootars...
1
11
111
1111
etc...
in each case, you divide (say 11111) by n, what ever the remainder you get (it has to be between 0 and n-1) send that kabootar to the pinjra which has the remainder number.
(eg suppose n=4, send first kabborar (1) to 1 , second kabootar (11) to (11/4 = 2*4+3)  plus remainder 3, third kabootar (111) to 3 (If you divide 111 by 4 you get remainder 3) etc...)
Now you must get one hole where there are two kabootars..(In our example  111 and 11) which have the same remainders .. subtract smaller from the other... the difference is obviously divisible by n and, of course it will look like (1111.....) -(111...) = 111....000
which will have ankan=2

Note: The problem is similar to one of my problems from a math contest for high school students... and yes, some times, it is hard to judge "hardness" of such problems, but very similar problems are being asked from time to time.

Posted: **28 Aug 2008 05:09**

SK Mody wrote:
Amber G. wrote:Rumor is that a new "largest known prime" (mersenne prime number) number is found..
It would be interesting to know if this has any implications for cryptography.

The Mersenne prime search project has been going on for years, and other than eating up CPU cycles that could otherwise be used for code breaking, I don't think there are any implications for cryptography.

In fact, other than being able to claim "largest known prime" and laying another possible claim to "largest co-operative computing effort on the internet", I am not sure the project has any theoretical significance. The Lucas-Lehmer test used to check for primality is from 1930.

Posted: **28 Aug 2008 08:46**

Karan Dixit wrote: ArmenT,

I do not know about Ruby or Python. However, it is easy to do it in C# using .Net Framework function. But he is not allowed to use the .Net Framework functions. Were you able to do it in one minute without using .Net Framework functions?

Yeah, I did it the same way as Vriksh (i.e.) basic 8th grade arithmetic principles. Actually the longest part of the one minute was not thinking about it, but getting the syntax straight (I'd missed one of the parenthesis in my first try

Code: Select all

#!/usr/bin/env python
array = [1, 4, 2, 3, 1]
# Here's my one line solution
answer = sum(array) - ((len(array) - 1) * (len(array)))/2
print answer

In other languages that don't necessarily have a sum() function, you can always iterate through the array and get the sum manually. The idea is the same, except it won't be a one liner in some other languages.

Other solutions would include sorting the array (surely this kid can at least write a bubble sort from scratch, can't he?) and then iterating to find when the element is not the same as the array index (or index - 1 for 0-based array languages). Third solution would be to use a hash structure (or another array the same length as the original array) and add each item into the hash. If the cell is already occupied, then you've found your duplicate.

What kinda test is this where they allow you a whole day to seek outside help for answers.

Posted: **28 Aug 2008 11:32**

Nandu wrote:
SK Mody wrote: It would be interesting to know if this has any implications for cryptography.
In fact, other than being able to claim "largest known prime" and laying another possible claim to "largest co-operative computing effort on the internet", I am not sure the project has any theoretical significance. The Lucas-Lehmer test used to check for primality is from 1930.

Well, one nice thing about Mersenne primes is its relationship to perfect numbers. Basically there is a proof by Euclid that states that if 2^p -1 is prime (this is the definition of a mersenne prime), then (2^p-1) * (2^(p-1)) is a perfect number. For those who don't know what a perfect number is, any number that is equal to the sum of its factors is a perfect number. 6 is one example (6's factors are 1, 2 and 3 and 1+2+3 is 6) and 28 is another (28's factors are 1, 2, 4, 7, 14 and 1 + 2 + 4 + 7 + 14 = 28)

So finding the largest mersenne prime automatically finds the next largest known perfect number as well.

Posted: **28 Aug 2008 20:06**

Interesting that wiki still hasn't the news about new found prime, (well people are going to wait till it gets verified by another computer)..but google news finds in science.slashdot.org now..

An anonymous reader writes "The Great Internet Mersenne Prime Search (GIMPS) has apparently discovered a new world-record prime number. A GIMPS client computer reported the number on August 23rd, and verification is currently under way. The verification could take up to two weeks to complete. The last Mersenne prime discovered was over 9.8 million digits long, strongly suggesting that the new value may break the 10 million digit barrier — qualifying for the EFF's $100000 prize!"

And speaking of numbers like (2^n +-1)has any one found factors of 2^58+1 (other than 5) ...

Posted: **28 Aug 2008 20:23**

Amber G. wrote:
And speaking of numbers like (2^n +-1)has any one found factors of 2^58+1 (other than 5) ...

Yeah, but I am not going to post or even claim it because all I did is type in factor _number_ on my linux box.

The largest factor is the sum of just three powers of two, but again, I have no idea how to derive it manually.

Bharat Rakshak

BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: Vinaji's post

Re: BR Maths Corner-1

Re: Vinaji's post

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1

Re: BR Maths Corner-1