Let's discuss Mathematics

[ParadigmShifter]

An N sided table has N symbols to choose from 0, ..., N-1, that's all. EDIT: And a string length of N of course, for the N vertices. You can imagine them as arrows rotated by 360/N degree steps.

The thing you need to recurse is the nested for loops, shouldn't be too hard. All the other functions can just take a list length as parameter.

Just kidding about the text representation thing... good work!

EDIT: Maybe there are 3 possibilities for a 2 sided table... 00, 01 and 10. 4th beer prevents me from doing any more maths atm.

EDIT2: That's why I said "clearly" when I claimed there are only 2 possibilities for N=2. Classic hand-waving dodge there

EDIT3: Yep, there are 3 possibilities for N=2, these are 00 (=11 rotated thru 180 degrees), 01 and 10 (arrows pointing towards vs. away from). Clearly

 

[LulThyme]

A factory makes tables of 40 x 40 cm^2, the top is made out of 4 identical tiles of 20 x 20 cm^2. These tiles are asymmetrical (imagine they contain an arrow pointing in a direction). By rotating these tiles, different tables can be made. For example:

up up
down down

However, some of these possibilities are identical, for example, the table

up up
down down

is identical to the table

left right
left right

by rotating it 90 degrees. How many unique tables can this company make?

This is a typical application of "the lemma that is not Burnside's".
By the way, I am a little puzzled why noone in the thread considered this comment :

Depends on how many different veneers are available

The original problem doesn't say, but I'll assume that available tiles always have the arrow poiting in one of four directions (orthogonally towards a side), since this is the assumption everyone seems to be using.

Note that the problem says we are counting tables, not tops. Two tops that are identical under a reflection (but not a rotation) do NOT yield two identical tables , (I'm assuming tables have legs).
In other words, the group under consideration is the cyclic group of order 4.

The set we are working on has 4^4 elements.
All of these are fixed by the identity element.
4^2 of them are fixed by the half rotation (you simply need to specify two adjacent tiles), and 4^1 of them by each quarter rotations (you only need to specify a single tile to determine the others).

By Burnside's Lemma, the number of orbits is simply (1/4) (4^4+4^2+2*4^1)=70.

EXTRA CREDIT :
For an interesting but not much more difficult question, try to answer the same question but counting "tops" instead of tables.

 

[LulThyme]

An N sided table has N symbols to choose from 0, ..., N-1, that's all. EDIT: And a string length of N of course, for the N vertices. You can imagine them as arrows rotated by 360/N degree steps.

The thing you need to recurse is the nested for loops, shouldn't be too hard. All the other functions can just take a list length as parameter.

Just kidding about the text representation thing... good work!

EDIT: Maybe there are 3 possibilities for a 2 sided table... 00, 01 and 10. 4th beer prevents me from doing any more maths atm.

EDIT2: That's why I said "clearly" when I claimed there are only 2 possibilities for N=2. Classic hand-waving dodge there

EDIT3: Yep, there are 3 possibilities for N=2, these are 00 (=11 rotated thru 180 degrees), 01 and 10 (arrows pointing towards vs. away from). Clearly

You have a "cyclic" string of length n, with entries in Zn. You are considering the number of orbits under the action of the cyclic group of order n, where the generator adds one to each entries as it rotates.

Let us use Burnside's Lemma.

There are n^n strings, all of them fixed by the identity.
Now, suppose we have an element g of order (n/m) in the group. It isn't hard to see that it fixes exactly n^(n/m) strings. To see this, simply note that you can specify the first (n/m) elements of a particular string as you wish, and then the rest are completely determined by the fact that this rotation will preserve them.

Hence, the answer is sum_{0 =<i =< n-1} (n^(gcd(i,n)-1).
For example, for n=4, we get again : 4^3+4^0+4^1+4^0=70.
In general, if n is prime, then gcd (i,n)=1 unless i=0, hence we get n^(n-1)+(n-1).
For example, for n=2, we get 2^1+1=3, for n=3, we get 3^2+2=11 and for n=5 we get 5^4+4=629.
So the sequence starts :
1,3,11,70,629
and we get sequence A056665
http://www.research.att.com/~njas/sequences/A056665 on the Online encyclopedia.

 

[ParadigmShifter]

Cool thanks never heard of Burnside's Lemma before.

I never did group theory at uni though only combinatorics.

EXTRA CREDIT :
For an interesting but not much more difficult question, try to answer the same question but counting "tops" instead of tables.

You mean ones that are different considering both rotation and reflection?

 

[LulThyme]

You mean ones that are different considering both rotation and reflection?

Exactly

 

[dutchfire]

Answer:
There's a total of 4^4=256 tables. 4 of those are rotation symmetrical. For example:
ur
ld
These tables are unique.

4^2-4=12 are "mirror symmetric" (don't know if that's the correct English term) but not rotation symmetrical. These tables always come in 2, for example:
uu = lr
dd = lr

256-12-4=240 tables are without symmetry. These come in groups of 4, for example:
uu = ur = dr = ll
lu = rr = dd = ld

Total: 4 + 12/2+240/4=70.

I used this question, and the previous one, for a quiz at university. I found both of them in old editions of the "Maths Olympics", the Dutch edition of the [wiki]International Mathematicl Olympiad[/wiki].

 

[LulThyme]

Answer:
There's a total of 4^4=256 tables. 4 of those are rotation symmetrical. For example:
ur
ld
These tables are unique.

4^2-4=12 are "mirror symmetric" (don't know if that's the correct English term) but not rotation symmetrical. These tables always come in 2, for example:
uu = lr
dd = lr

256-12-4=240 tables are without symmetry. These come in groups of 4, for example:
uu = ur = dr = ll
lu = rr = dd = ld

Total: 4 + 12/2+240/4=70.

I used this question, and the previous one, for a quiz at university. I found both of them in old editions of the "Maths Olympics", the Dutch edition of the [wiki]International Mathematicl Olympiad[/wiki].

This is wrong. For one thing, we already found that there were 70 different tables. Different tops give different tables but some tables that were different come from the same tops, hence the answer must be less than 70.

Here are some holes in your reasoning :

-some tops have "half-rotation" symmetry, but not "quarter rotation symmetry" neither reflection symmetry.
For example,
LL
RR
-Note that there are also two types of reflection symmetries : up-down and left-right. (Explain why no table has diagonal reflection symmetry?)
-Tops with no symmetries come in groups of 8, not 4. For example,
uu
ur
is in the same group as
uu = ur = dr = ll
lu = rr = dd = ld
by reflecting the first one vertically.

Here's a hint:
there are 216 configurations with no symmetries.

 

[dutchfire]

It's the answer to the tables question I asked earlier, not to the tops question

 

[ParadigmShifter]

This site is cool and amusing, they sell Klein Bottles

http://kleinbottle.com/

 

[dutchfire]

These elegant bottles make splendid gifts, outstanding classroom displays, and inferior mouse-traps.

Filling instructions for your Acme Klein Bottle:

I suggest keeping your Klein Bottle dry, mainly because it's hard to clean once wet. But if you want to explore hydrodynamics of onesided containers, here's a few hints.

Don't just pour water into your Acme Klein Bottle -- the water will fill the sidearm and then vapor lock.

Instead, hold your bottle horizontally under water in a basin, bucket, or sink. Rotate it around its main axis; with each rotation, some air will bubble out. Once filled, add a drop of food coloring.



You can (but don't have to) seal your filled Klein Bottle with a cork. For Acme's Classical and Bottom-Mouthed Erlenmeyer Klein Bottles, use Acme Cork part #713-9b, $350. These corks are also available for free at most good Italian restaurants.

Thousands of Important Professors, Nobel Laureates, and High Scoring Bowlers have told us that ACME Klein Bottles have improved their lives, solved their interpersonal problems, and Fulfilled their Dreams... but they're all lying.

Actually an Acme Klein Bottle won't do anything for you ... it'll do things for us. Yep, after you purchase an Acme Manifold, we'll have enough money that we won't care about tenure.

Now, before inflation burns away more of your precious lucre, invest in a genuine Acme Klein Bottle. Do it now and you may not regret it later.

Nice site!

 

[peter grimes]

You gotta love honesty!

Are you guys familiar with the classic catalogue outfit American Science and Surplus? The product descriptions are stellar. The odd thing is that many of the higher-quality items [optics, motor trains, electronic components] are surplus Russian gear

 

[Mise]

Hi hi, I read in an internets comic that if you assigned a letter to each number (e.g. a = 01, b = 02, etc), then somewhere in Pi would be Shakespeare's plays written out in full. Now, I'm not convinced about this... you could certainly conceive an irrational number that contained no 4's, for example -- can't you? I mean, an irrational number just needs to be inexpressible as n/m where n, m are integers -- a number meeting that criteria could nonetheless have properties that preclude the string containing every single combination of numbers. Or, more strictly, there's no reason to believe that it has the property of containing every single combination of numbers, right??????

 

[ParadigmShifter]

I got asked about that at a job interview once

It's all to do with whether the irrational number is normal in a certain base (base 26 for example for just letters say).

It's unknown whether pi is normal in any base but it is conjectured to be so.

http://www.economicexpert.com/a/Normal:number.htm

Incidentally, in the job interview I said basically what you said Mise, and also said that just because the Mandelbrot set is infinitely complex and non-repeating doesn't mean that you will find a picture of the Mona Lisa therein.

Incidentally, I didn't get the job, despite getting the best results in the C programming test they had ever seen

EDIT: And here's Mathworld on the subject

http://mathworld.wolfram.com/NormalNumber.html

 

[Mise]

Huh, yeah, the Mandelbrot thing is intuitively appealing... This is the sort of thing that would keep me awake at night if I were a mathemagician

 

[Atticus]

somewhere in Pi would be Shakespeare's plays written out in full.

While we may not be able to prove this as false, it could be proven true. So let's start a project of coding Shakespeares plays into numbers.

The irrationality of pi isn't sufficient condition. For example number
0.1010010001000010000010000001....
isn't rational since it has no recurring cycle, but contains only digits 0 and 1.

These kinds of questions don't really bug me at all. There's always some things you don't know.

Here's a number I constructed for these kinds of questions:
0.12345678910111213141516171819202122232425262728293031323334353637...
So the number lists in order every natural number, and it has all the works of Shakespeare in it. Also every other book ever written, and those not yet written too. It also has movie of George Bush having sex with hippopotamus in mpg format, it has all the possible variations of it, and in some of them Osaman Bin Laden is in the action too. It contains secrets so arcane that I'm in great danger for publicly announcing the number.

Notice that there's quite many this kind of numbers. You can for example permutate the order how numbers of length 4 are written down. Or you can permuatate by length, or with both. (They are for example dense in [0,1], i.e. you can approximate any given number with any given precision with these).

This number however isn't very exciting. It's rather dull actually, because it's artificially made so that anything can be found in it. And that is possible because we allow desimals that go on without end, so there's nothing mysterious about it. This might illuminate why the pi thing doesn't shake so much mathematician's world: Infinity allows you to do pretty odd things.

By saying that Hamlet could be found in pi, you imagine that you really can find it. But there's very strong possibility that it's so far you can't even imagine. The digit from which it would begun could be bigger than can ever in the history of universe written down. Even if every atom in the universe was supercomputer writing it down (by let's say raising 9 to the 9th power succeasively). Or it could be much much bigger.

 

[Mise]

"0.12345678910111213141516171819202122232425262728293031323334353637..."

If you took the string "12345678910111213141516171819202122232425262728293031323334353637..." and called it X, then created another string by putting a 2 in front of it (i.e. 2123456789101112...), would X contain this new string?

 

[Atticus]

No it wouldn't. It contains any finite string.

 

[Atticus]

1. Is there a way to write maths in bbcode?

2. Maybe I should do something serious, but it's monday, so this thing seems very urgent to me:

Here's a number I constructed for these kinds of questions:
0.123456789101112131415161718192021222324252627282 93031323334353637...
So the number lists in order every natural number, and it has all the works of Shakespeare in it.

By hat-estimation (drawn from the hat) normal book has 40 lines/page and 40 char/line. Hamlet is about 100-150 pages long (too lazy to verify at moment). Because it's not normal prose, I suppose it's 100 pages to compensate for shorter lines. So it contains about 160 000 char, of which each takes two numbers to code, so it would be 320 000 digits.

Let's now consider where to seek Hamlet in the number mentioned in the quote.

There's 10^k -1 natural numbers whose length is k digits or less.
So there's 10^k - 10^(k-1) natural numbers whose length is exactly k digits.
Therefore in the number there's
\sum_{k=1}^{n} k (10^k -10^{k-1} )
digits before first of the natural numbers of length n appears (you know what I mean, even if it's not formally stated, that is the first occurence of sequence 10^n).

So you'll find Hamlet starting after digit number
\sum_{k=1}^{160 000} k (10^k -10^{k-1} ) ,
but before the digit
\sum_{k=1}^{161 000} k (10^k -10^{k-1} ).

Exercises:
1. First thought would be that you can find it by coincidence before that digit. Prove that this isn't true (you'll have to make few assumptions to do it)
2. For the Excell-using abominations: Try to write down the numbers we obtained for the endpoints of the interval where Hamlet is to be found.
3. The idea behind finding Hamlet in pi is that pi's digits can be considered random, and when carried out endlessly, even the most unprobable thing will happen. So suppose you have random real number x in ]0,1[, it's supposed to be our pi. If the probability that Hamlet has started by the n:th digit of x is P(n), how big n shoul be that P(n)=0.01? How big it should be that P(n)=0.50?

 

[Mise]

I have a question again!

I know via excel that lim n->inf { ((n-1)/n)^n } = 1/e
However I cannot prove it... I tried using ln and whatnot but it still wouldn't work!

(For those of you that need a reason for doing this, it will answer this question: if the probability of an event occuring is 1/n, what is the probability of that event occuring after n trials? So if someone said there's a 5% chance of dying when you cross the road, there'd be a ~2/3rds chance of dying after crossing the road 20 times. It's useful to know that approximation, but I wanna know how to derive it!!)

 

[Perfection]

to find the limit of x

x = (n-1)/n)^n

the trick to this is to find the related limit

y = ln x = ln ((n-1)/n)^n)

then just take x = e^y

The first step is y = n*ln ((n-1)/n)

note that:
n goes to infinity
ln ((n-1)/n) goes to zero
So it's just L'Hôpital's from there on out. I'd do the full proof but I gotta go to work.

edit: (oh wait, you tried using ln? where's the problem? seems straight forward to my cursory look)