I wish I had found a better problem for the previous post. Initially I wanted to find a solution to the 2-player game where you have n columns, and m_i rings in the ith column, and each player can take as many rings as s/he wants from any one of the colums (but is not allowed to touch more than one column, and must take at least one ring). The player who takes the last ring loses. I tried to prove it using some sort of nested induction, but I failed. I did manage to solve it for the special case n=2, but then again, that is probably not very hard to do.
Anyway, later I found out that the game is called Nim, and I read it's solution and proof in wikipedia. It is safe to say I could have never solved it within the end of this semester.
Overall, I would say this was a very nice course. Regular expressions, CFG's, FSA's, and PDA's were of much greater interest to me than I thought they would be (which is not to say that I thought they would be boring). I'm definitely going to pick up a more advanced book on the subject to study during the summer. Either that or a book on computability (if anyone reading this has any suggestions, it would be nice if you told me in a comment).
I did think that the tests were marked a bit too harshly and marks were taken off for fairly trivial things, but that's ok.
Friday, December 5, 2008
Math problem
First, some definitions and results that will be assumed to be true (and in fact are true, but will not be proven here):
Definitions:
Rn is the set of all n-tuples with real coordinates.
If A is a subset of Rn, A is a rectangle if A = [a1, b1]x[a2, b2]x...x[an, bn] (where ai, bi \in R, and ai <= bi for all 1<=i<=n). If A is a rectanlge in Rn then let the volume of A be vol(A) = (b1-a1)*...*(bn-an). If f:Rn -> R and A is a rectangle in Rn, then f|A is the function from A to R defined by f|A(x) = f(x), \forall x \in A.
If f:A -> B (A, B are any sets), define the graph of f to be F = {(x, f(x)) | x \in A}. (So F is a subset of AxB)
A partition P of a closed interval [a, b] is a non-decreasing, finite sequence of numbers t0, ..., tk such that t0 = a and tk = b.
If f:A -> R (where A is a rectangle in Rn), a partition P of A is P = (P1, ..., Pn) where Pi is a partition of [ai, bi] (where A = [a1, b1]x[a2, b2]x...x[an, bn]);
mS(f) = inf{f(x) | x \in S}, MS(f) = sup{f(x) | x \in S} (where S is a subrectangle formed by P); L(f, P) = Sum(mS(f)*vol(S), over all S's in P), U(f, P) = Sum(MS(f)*vol(S), over all S's in P); and f is integrable if and only if
sup({L(f, P) | P is a partition of A}) = inf({U(f, P) | P is a partition of A}). We say that sup({L(f, P)}) is the integral of f.
If S is a subset of Rn we say that S has measure 0 if, for any e > 0, there is a sequence of closed rectangles A1, A2, ... such that S is a subset of the union of all Ai's, and Sum(vol(Ai), over all i \in N) <> R is integrable if and only if for any e > 0 there is some partition P of A such that U(f, P) - L(f, P) <>= 1, there is a set of countably many closed rectangles that are subsets of Rn, the union of all of which is Rn (this is easily proved by induction on n: for n = 1, ... [-1, 0], [0, 1], [1, 2], ... is the obvious candidate, and for n+1 the collection that satisfies the required properties is the result of taking the cartesian product of each set in the collection for R1 with each set in the collection for n).
So, I decided that the math problem I will solve as a SLOG requirement is this: if f:Rn -> R is a function such that f|A is integrable for any closed rectangle A \in Rn, does f's graph have measure 0?
The answer is yes. Intuitively, this is because for every point in Rn we only have one point in R, and f is integrable so it is fairly well behaved; so in some sense, in most places the graph is infinitely thin and we can chose rectangles that are as thin as we want and still manage to cover it.
Let O be a collection of countably many closed rectangles in Rn such that their union is Rn. For any A \in O, we will prove that the graph of f|A has measure 0. For any e > 0: we know that f|A is integrable, which means that there is a partition P such that U(f, P) - L(f, P) = Sum(MS(f)*vol(S), all S's in P) - Sum(mS(f)*vol(S), S's in P) = Sum((MS(f)-mS(f))*vol(S), all S's in P) < e (%%). Let Q = {Sx[mS(f), MS(f)] | S is a subrectangle of P}. By the definition of the volume of a rectangle, the sum of the volumes of all the rectangles in Q is Sum(vol(S)*(MS(f) - mS(f)), S is a subrectangle of P) < e by (%%).
For any (x, y) in the graph of f|A, y = f(x) (by definition of graph). Since P is a partition of A, there must be some subrectangle S' of P such that x \in S'. By definition of mS(f) and MS(f), mS'(f) <= f(x) <= MS'(f), which means that f(x) \in [mS'(f), MS'(f)], which means that (x, f(x) \in S'x[mS'(f), MS'(f)] \in Q. So for any (x, y) in the graph of f|A, (x, y) in some rectangle in Q. So Q covers the graph of f|A. As we just showed, the sum of the volumes of all rectangles in Q is smaller than e. So by definition of measure 0, the graph of f|A has measure 0.
Since there are countably many rectangles in O, and since their union is Rn it follows that the graph of f is the union of the graphs of f|A (A \in O). Since each of those graphs has measure 0, and since there are countably many of them (one for each member of O, which has countably many members), it follows that the graph of f has measure 0.
Definitions:
Rn is the set of all n-tuples with real coordinates.
If A is a subset of Rn, A is a rectangle if A = [a1, b1]x[a2, b2]x...x[an, bn] (where ai, bi \in R, and ai <= bi for all 1<=i<=n). If A is a rectanlge in Rn then let the volume of A be vol(A) = (b1-a1)*...*(bn-an). If f:Rn -> R and A is a rectangle in Rn, then f|A is the function from A to R defined by f|A(x) = f(x), \forall x \in A.
If f:A -> B (A, B are any sets), define the graph of f to be F = {(x, f(x)) | x \in A}. (So F is a subset of AxB)
A partition P of a closed interval [a, b] is a non-decreasing, finite sequence of numbers t0, ..., tk such that t0 = a and tk = b.
If f:A -> R (where A is a rectangle in Rn), a partition P of A is P = (P1, ..., Pn) where Pi is a partition of [ai, bi] (where A = [a1, b1]x[a2, b2]x...x[an, bn]);
mS(f) = inf{f(x) | x \in S}, MS(f) = sup{f(x) | x \in S} (where S is a subrectangle formed by P); L(f, P) = Sum(mS(f)*vol(S), over all S's in P), U(f, P) = Sum(MS(f)*vol(S), over all S's in P); and f is integrable if and only if
sup({L(f, P) | P is a partition of A}) = inf({U(f, P) | P is a partition of A}). We say that sup({L(f, P)}) is the integral of f.
If S is a subset of Rn we say that S has measure 0 if, for any e > 0, there is a sequence of closed rectangles A1, A2, ... such that S is a subset of the union of all Ai's, and Sum(vol(Ai), over all i \in N) <> R is integrable if and only if for any e > 0 there is some partition P of A such that U(f, P) - L(f, P) <>= 1, there is a set of countably many closed rectangles that are subsets of Rn, the union of all of which is Rn (this is easily proved by induction on n: for n = 1, ... [-1, 0], [0, 1], [1, 2], ... is the obvious candidate, and for n+1 the collection that satisfies the required properties is the result of taking the cartesian product of each set in the collection for R1 with each set in the collection for n).
So, I decided that the math problem I will solve as a SLOG requirement is this: if f:Rn -> R is a function such that f|A is integrable for any closed rectangle A \in Rn, does f's graph have measure 0?
The answer is yes. Intuitively, this is because for every point in Rn we only have one point in R, and f is integrable so it is fairly well behaved; so in some sense, in most places the graph is infinitely thin and we can chose rectangles that are as thin as we want and still manage to cover it.
Let O be a collection of countably many closed rectangles in Rn such that their union is Rn. For any A \in O, we will prove that the graph of f|A has measure 0. For any e > 0: we know that f|A is integrable, which means that there is a partition P such that U(f, P) - L(f, P) = Sum(MS(f)*vol(S), all S's in P) - Sum(mS(f)*vol(S), S's in P) = Sum((MS(f)-mS(f))*vol(S), all S's in P) < e (%%). Let Q = {Sx[mS(f), MS(f)] | S is a subrectangle of P}. By the definition of the volume of a rectangle, the sum of the volumes of all the rectangles in Q is Sum(vol(S)*(MS(f) - mS(f)), S is a subrectangle of P) < e by (%%).
For any (x, y) in the graph of f|A, y = f(x) (by definition of graph). Since P is a partition of A, there must be some subrectangle S' of P such that x \in S'. By definition of mS(f) and MS(f), mS'(f) <= f(x) <= MS'(f), which means that f(x) \in [mS'(f), MS'(f)], which means that (x, f(x) \in S'x[mS'(f), MS'(f)] \in Q. So for any (x, y) in the graph of f|A, (x, y) in some rectangle in Q. So Q covers the graph of f|A. As we just showed, the sum of the volumes of all rectangles in Q is smaller than e. So by definition of measure 0, the graph of f|A has measure 0.
Since there are countably many rectangles in O, and since their union is Rn it follows that the graph of f is the union of the graphs of f|A (A \in O). Since each of those graphs has measure 0, and since there are countably many of them (one for each member of O, which has countably many members), it follows that the graph of f has measure 0.
Subscribe to:
Posts (Atom)
