Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
WTF? My internet connection went down for almost the entire weekend, and now that it's back, I'm kinda surprised at the reception of this movie.
As the title and the submission suggest, I made this as a joke and really had no intention of getting it published. This sequence is one I have read about / someone told me way back when I played chess competitively, I didn't even know it had a name or where to find it on the internet.
If it wasn't noticed yet, the combination is entirely forced, (actually I find it amazing how much the CPU thinks before doing a forced move), Black has only one choice to move, there's no luck manipulation involved. Is the position impressive? Yes, but not about anything that has something to do with a video game, it'll be the same thing if shown on a chess board.
Since there's some relevant support, I'll keep this up, but it's definitely not something to publish, in my opinion.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Damn, those were the most amazing 8955 frames of my life! The sheer mind-blowing awesomeness of this movie made it perfectly clear to me why exactly 8955 frames are necessary, showing that the main problem with most movies in the site is that they are shorter or longer than 8955 frames.
Epiphanic yes vote, and hoping that it obsoletes all TAS material that doesn't last that amount of time.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
A good joke TAS has AT LEAST one of these properties:
* is funny;
* is interesting, despite not having anything to do with the site;
* has an encode ready, so that people don't need to bother download it;
* is submitted on April 1st.
This movie fails to have any of those, I vote NO.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Consider a regular polygon inscribed in a unit circle. The semiperimeter times the "apótema" (don't know the name in English, it's the segment that connects the center of the circle to the midpoint of the regular polygon's side) gives the area.
The side of the regular polygon of 2n sides is L(2n) = sin (180º/2n). Notice that L(2n)^2 = sin^2 (180º/2n) = 1/2 (1 - cos (180º/n) ) = 1/2 - sqrt(1 - L(n)^2).
So, L(2n) = sqrt(1/2 - sqrt(1 - L(n)^2)). If we substitute L(4) = sqrt(2)/2, we get a formula, that's not very pretty. Take a look:
L(8) = sqrt(2 - sqrt(2))
L(16) = sqrt (2 - sqrt(2 + sqrt(2))
L(32) = sqrt (2 - sqrt(2 + sqrt(2 + sqrt(2)))
Basically, a polygon with 2^(n+1) sides has n nested radicals in the formula. Its semiperimeter is the sum of the lengths of half its sides, so 2^n * L(2^(n+1)). Since a regular polygon tends to the circle and the "apótema" tends to the radius, when n goes to infinity the area will be:
A = lim (n-> infty) 2^n * sqrt(2 - sqrt(2 + sqrt(2 + sqrt ( 2 + ... )))) {n radicals}
Notice that there are many ways to compute pi, I posted this method because Warp seemed to want a geometric argument, this limit is not trivial, in fact, much time passed before a proof of its irrationality was found, and it's also transcedental, meaning there's no way to represent it with finite radicals or any polynomial root.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I solved 5) again. Interestingly, despite my mistake, the proposition is true for both 2005 and 2011. Fermat's little theorem is not necessary, just modular arithmetic. I'll solve it for 2011.
1 + 2 + 3 + ... + 2011 = 2011*1006
By Euclid's algorithm, gcd(2011,1006) = gcd(1006,1005) = gcd (1005,1) = 1
Thus, 2011 and 1006 are coprime. To prove that the sum is a multiple of the product, it suffices to prove that it's divisible by 2011 and 1006.
The sum 1^2011 + 2^2011 + ... + 2009^2011 + 2010^2011 + 2011^2011 can be expressed in mod 2011 by 1^2011 + 2^2011 + ... + (-2)^2011 + (-1)^2011 + 0^2011.
Since 2011 is odd, k^2011 = - (-k)^2011, so k^2011 + (-k)^2011 = 0, and this proves that the sum is a multiple of 2011.
For 1006, we get the sum mod 1006 as 1^2011 + 2^2011 + ... + (-2)^2011 + (-1)^2011 + 0^2011 + 1^2011 + ... + (-1)^2011.
It's similar to the previous case, this sum is 0 and 1006 divides the sum. It's an exercise to prove for 2005 :)
I'll give a hint for 4):
There are basically two properties that allow us to evaluate a sum. One was used in 5), it's when we can pick to terms that have some symmetry and evaluate it. The other is when it's a telescoping sum, that is, its general term can be expressed as f(n) - f(n-k) or something like that. This technique is used in 4). Also, note that k^2 + 3k + 1 = (k+1)(k+2) - 1.
Additionally, andymac, I've seen Fermat's little theorem when I was in high school. It was stated without proof, though, so I had to wait until university to see its demonstration. You can get a very good background on number theory with this book. IIRC the most complicated chapters demanded only the knowledge of finite fields, which most institutes offer at the first year of the course.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I think you should revise your calculations for 3), because the reasoning is correct, but the answer should be 44.
We basically want to find the smallest m that satisfies 10^m = 1 (mod 89). By Fermat's little theorem, since 89 is a prime, we have a^(p-1) = 1 (mod p) -> 10^88 = 1 (mod 89). So, the smallest integer is a divisor of 88 (1,2,4,8,11,22,44,88).
10 = 10 mod 89
10^2 = 100 = 11 mod 89
10^4 = 11^2 = 121 = 32 mod 89
10^8 = 32^2 = 1024 = 44 mod 89
None of these worked.
10^11 = 10^8 * 10^2 * 10 = 44 * 11 * 10 = 55 mod 89
10^22 = 55^2 = 3025 = 88 = -1 mod 89
10^44 = (-1)^2 = 1 mod 89 <- Hit!
So, 10^44 - 1 is divisible by 89, and is a number with 44 nines.
Any ideas for 4) and 5)?
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
1) Show that, if p is a prime larger than 3, then p^2 - 1 is divisible by 24.
2) p4wn3r writes 3^2011 consecutive 7's in a blackboard. Is this number divisible by 3^2011?
3) The number 1/89 is written in decimal form. Determine the length of the period of the digits.
4) Let S = 1! * 1 + 2! * 11 + ... + k! * (k^2 + 3k + 1) + ... + 200! * (200^2 + 3*200 + 1)
Find the remainder of S when divided by 2004.
5) Prove that 1^2011 + 2^2011 + 3^2011 + ... + 2011^2011 is divisible by 1 + 2 + 3 + ... + 2011
Good luck!
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Yeah, that's totally right. I wish I could solve the present IMO problems as easily as I can solve the archaic ones... Things have come a long way.
Another way is to use Bézout's identity.
Since -2*(21n+4) + 3(14n + 3) = 1, therefore, 1 is the gcd of the two numbers, so the fraction is irreducible.
Completely equivalent, but only uses one line =P. Anyone in the mood for harder number theory problems?
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I don't know Python and couldn't understand much of what you coded, but I couldn't spot any indication that you used a queue as an auxiliary structure. Using a queue can make your code more efficient, because the algorithm seems to be a variation of a breadth-first search.
If you actually used a queue there, then ignore this post. :P
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Randil wrote:
When it comes to non-integer dimensions, you enter the field of Hausdorff dimension and fractal dimensions. An example of a set of non-integer dimension is the cantor set C - in terms of cardinality, C is as large as R, but in terms of length, C is just a single point. Therefor the dimension of C falls between 0 and 1, in this case 0.631. So I guess a pi-dimensional cube would be an object with 3-dimensional length (where in this case "length" is defined by some metric) but with some cardinality-properties of a 4-dimensional object.
Interesting...
With the idea of fractal dimensions and the Cantor set, I could create a set with pi-dimension. First, let's see why the Cantor set has that dimension. Let's try to find the minimum amount of balls and their "radius" to cover the figure at each iteration. The only ball in R is an interval, and it needs to have the length of the sub-intervals f the Cantor set at the n-th iteration. We have:
Now, its dimension will be given by , which matches the number.
It follows from intuition that since pi>3, we can't construct a set with pi dimension starting from a 3-dimensional space, so we have to go to the fourth dimension, where geometric interpretations will no longer help us. Let S^4 denote S x S x S x S. Let's construct a more general Cantor set, which partitions the interval in more general quantities and extends it to the fourth dimension by cartesian products. The first iteration looks like this:
I'll consider the balls to cover this interval to be boxes, the same result would be achieved with the Euclidean metric, but there would be more calculations. This way, we can get:
We want to pick a t so that the dimension of this set is pi, in order to do this, we evaluate its dimension:
So, by constructing this set using , it'll have a dimension of pi.
arflech wrote:
Is the consistency of the definitions still an open mathematical question?
Even arithmetic has trouble being totally reduced to logic, let alone the more advanced concepts. Gödel's incompleteness theorems struck a heavy blow to the program of finding a consistent theory for arithmetic. There's still hope to do it though, by proving its consistency with a theory that doesn't satisfy the conditions of Gödel's theorems, so it's still open.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
petrie911 wrote:
Here's a fun question. Prove that there is no infinite set smaller than the integers.
The proof follows immediately from the axiom of choice. Let S be an infinite set, according to the axiom of choice, I can select an element from S. Call it x1. Since S is infinite, S - {x1} is infinite too, and again I can pick an x2 from it . Through analogous recursive reasoning, I can pick an xn from S - {x1,x2,...,x_n-1}.
I have then defined an injection from N to S, thus card(S)>=card(N), which proves the statement, and, I'm not really a fan of this part of mathematics and don't find it fun. =P
Warp wrote:
(What would it even mean to have a "pi-dimensional cube"?)
I missed this part before. I don't remember very well non-integer dimensions, they're defined differently from integer ones. I think it had something to do with balls (sets of all elements x such that d(x,a)<r for a given element a), and how fast the amount of balls needed to cover the figure diverges as r gets smaller. I may be saying stupid stuff though...
What I do remember is that there isn't only one formal definition and they're adopted depending on the mathematical interest.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
To define the dimension of a space, you need to determine a base. A base is a set that, for any element in your space, you can write it uniquely as a linear combination of the base elements. The space of all polynomials of degree 3, for example, has dimension 4, because:
P(t) = a + b t + c t2 + d t3
This is a linear combination of the base {1, t, t2, t3}, it has four elements, so dimension four. However, if you consider the space of all polynomials, its base is {1, t, t2, t3... }, because for spaces that aren't finitely generated, the definition of a base is a little different. A set B is a base of a space V iff B is linearly independent and every element in V can be written as a linear combination of a subset of B. This is the case for the polynomials of any degree, its base is infinite and it has infinite dimensions. If the set also happens to be uncountable, then you have uncountably many dimensions, but this case is not very useful in practice.
We have a little trouble to think of a bijection from [0,1] to [0,infinity[ because we normally tend to think of continuous functions, and such mapping doesn't exist, because the image of a continuous function on a closed and bounded interval is always a closed and bounded interval too.
Consider this:
S = {1 , 1/2, 1/3, ... }
f(x) = {0, if x=0 ; -ln (1/(1/x + 1)), if x is in S ; -ln x, if x>0 is not in S}
This function is basically -ln x with a "shift" along the enumerable set {0,1,1/2,1/3 ... } to fix the problem of the point 0, where ln is not defined. This shift maps 0 to -ln 1 , 1/1 to - ln 1/2 , 1/2 to -ln 1/3 and so on.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Warp wrote:
p4wn3r wrote:
The other case is when the base is uncountable. The cardinality will be the same as the set of all real functions from R to R (R^R) . Using the same diagonal argument Cantor used to prove R is not enumerable, we can prove that the cardinality of R^R is 2^card(R), bigger than card(R). The generalized continuum hypothesis states that this cardinality is aleph-2, but it's unprovable in the most common axiomatization of mathematics. If you reject these axioms, a lot of things I wrote will no longer hold.
Do I understand correctly from what you are saying (and from what I have read at wikipedia about the continuum hypothesis) that whether there exists a one-to-one mapping between the set of reals in the range [0,1] (or, for that matter, the entire set of reals, it doesn't really make a difference AFAIK) and the set of points inside a unit hypercube of uncountably infinite dimensions or not cannot be either proven or disproven with "regular" set theory mathematics (for a definition of "regular" that goes well beyond my understanding of set theory)?
(Wow, that was one big sentence. I tried to split it up, but couldn't figure out a natural way of doing it without it becoming even more contrived...)
No, that's not what I was talking about. Perhaps my explanation was too fast.
Cardinal numbers are defined like this. Aleph-0 is the cardinality of N. A set has cardinality aleph-k if there's no bijection between it and any other set with cardinality aleph-i, i<k.
We can prove that the cardinality of R is 2^aleph-0 . The continuum hypothesis says that 2^aleph-0 = aleph-1 , implying that no set can have a cardinality between the natural numbers and the real numbers. With Zermelo-Fraenkel + axiom of choice set theory (the most common set theory), we can assume this proposition is true or false, and no contradictions will arise in the theory both ways. Thus, it's unprovable.
In the case of R^R, it's certainly true that its cardinality is larger than R (2^aleph-1 is larger than aleph-1), the (generalized) continuum hypothesis will only say if there's a set whose cardinality is between them or not.
Experienced Forum User, Published Author, Player
(42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Warp wrote:
p4wn3r wrote:
By your phrasing, I think you're asking whether the cardinality of [0,1] x [0,1] is larger than [0,1]. The answer is no. Dimensionality (or more strictly, the cartesian product of two sets) doesn't increase the cardinality of a set.
I assume from this that the set of points inside a unit cube would also be the same as those on a unit line, and likewise for a 4-dimensional unit hypercube, and so on. Is there any amount of dimensions that would make the set larger?
I made a mistake in my reply. The cartesian product of two sets A x B can have a greater cardinality than A and B, if both their cardinalities are finite. However, if they're infinite, card(A x B) = max {card(A),card(B)}.
So, if you consider that an n-dimensional space is the cartesian product of R n times, you can prove that the cardinality won't change by induction.
If you have an infinite dimensional space, there are two cases: the first one is if the base of your space is countable. This set will have the same cardinality as the set of all sequences of real numbers R^N (N denoting the set of natural numbers). And this set, being the set of all countable subsets of R, has the same cardinality as R.
The other case is when the base is uncountable. The cardinality will be the same as the set of all real functions from R to R (R^R) . Using the same diagonal argument Cantor used to prove R is not enumerable, we can prove that the cardinality of R^R is 2^card(R), bigger than card(R). The generalized continuum hypothesis states that this cardinality is aleph-2, but it's unprovable in the most common axiomatization of mathematics. If you reject these axioms, a lot of things I wrote will no longer hold.
Now, its dimension will be given by 
, which matches the number.
It follows from intuition that since pi>3, we can't construct a set with pi dimension starting from a 3-dimensional space, so we have to go to the fourth dimension, where geometric interpretations will no longer help us. Let S^4 denote S x S x S x S. Let's construct a more general Cantor set, which partitions the interval in more general quantities and extends it to the fourth dimension by cartesian products. The first iteration looks like this:
I'll consider the balls to cover this interval to be boxes, the same result would be achieved with the Euclidean metric, but there would be more calculations. This way, we can get:
We want to pick a t so that the dimension of this set is pi, in order to do this, we evaluate its dimension:
So, by constructing this set using 
, it'll have a dimension of pi.