Jump to content

e(ho0n3

Senior Members
  • Content Count

    112
  • Joined

  • Last visited

Everything posted by e(ho0n3

  1. It's been a while now and the [math][/math] tags are still not working. What's going on?!
  2. Hi everyone, I'm reading the paper "A Case for RAID" and I'm having difficulty understanding some of the calculations made. Example: So as X gets larger the above gets larger. This makes sense because it will take more time to repair more disks so the average number of second failures will grow. However, I'm not exactly sure how the formula is derived. Can anyone shed some light on this?
  3. How about graphing those functions of yours and seeing for yourself?
  4. I've attached a proof for all those interested. paths.pdf
  5. Thanks to a colleague of mine, I'm now aware of an error in my solution. Basically I didn't consider the repetition of the start and end vertices in the path. So... For question 1, assume j is even and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. How many odd-numbered index vertices are there? Easy, j/2. Once can choose j/2 vertices from N for the path P in nj/2 ways. How many even-numbered index vertices are there in P, excluding v[0] and v[j]? Easy, j/2 - 1. One can pick j/2 - 1 vertices from M for the path P in mj/2 - 1 ways. The answer then is nj/2mj/2 - 1. Question 2 is similar to question 1 (except M and N are reversed), so the answer is mj/2nj/2 - 1. For question 3, assume j is odd and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. There are (j + 1)/2 - 1 vertices having even index, excluding v[0]. There are also (j + 1)/2 - 1 vertices having odd index, excluding v[j]. Hence, the answer to the question is (mn)(j + 1)/2 - 1. I'll post a proof by induction that my solution is correct later (if it is correct that is).
  6. Here is a simple statement which I've yet to prove satisfactorily: Adding/deleting loops, parallel edges and edges in series does not affect the planarity of a graph. If a graph is planar, then removing anything from it does not create any edge crossings, so the graph remains planar. If a graph is not planar, then adding anything to it will or will not create any edge crosssings, so the graph remains unplanar. Now I have to show that adding (removing) loops, parallel edges and edges in series does not affect the planarity of a(n) planar (unplanar respectively) graph. This is were I stopped. I'm trying to think of a good argument which shows that a planar graph remains planar after the addition of loops. I'm guessing I'll have to describe a process that can add loops without creating edge crossings. Any tips?
  7. 1. If Carl lied, then Dave is telling the truth. If Dave lied, then Carl is telling the truth. Since exactly one of them told the truth, Andy and Bob are liars. Hence Dave "did it". 2. Seems impossible if Carl, Bob, Andy and Dave are distinct persons. 3. If what Andy and Dave said is true, then Carl did it.
  8. Rings are groups with fancier properties. Fields are rings with more fancy properties. Algebras are even fancier and so on I think. Primarygun: I have a list of tough discrete maths. questions which I haven't answered yet. I can send it to you if you want to. Just PM me.
  9. I know what an adjancency matrix is. Actually, I asked this question because I need to derive the jth power adjencency matrix of K[m,n]. In other words, if A is the adjencency matrix of K[m,n], derive a formula for the members of Aj.
  10. According to my book, a path can have repeated vertices. A path with no repeated vertices is called a simple path.
  11. So much for that...I still believe this problem is solvable using a delta-epsilon argument.
  12. Let K[m,n] be a complete bipartite graph and let M and N be the set of vertices with |M| = m and |N| = n such that every edge is incident on one vertex in M and one vertex in N. I have three questions: 1. If v and w are in M, how many paths are there from v to w of length j? 2. If v and w are in N, how many paths are there from v to w of length j? 3. If v is in M and w is in N, how many paths are there from v to w of length j? For questions 1 and 2, if j is odd, the answer is 0. For question 3, if j is even, the answer is also 0. (I can prove this if anybody is interested). For question 1, assume j is even and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. How many odd-numbered index vertices are there? Easy, j/2. Once can choose j/2 vertices from N for the path P in nj/2 ways. How many even-numbered index vertices are there in P, excluding v[0] and v[j]? Easy, j/2 - 1. If v[0] = v[j], one can pick j/2 - 1 vertices from M for the path P in (m - 1)j/2 - 1 ways. If v[0] ≠ v[j], one can pick j/2 - 1 vertices from M for the path P in (m - 2)j/2 - 1 ways. So the answer to question 1 is - nj/2(m - 1)j/2 - 1 if v[0] = v[j] - nj/2(m - 2)j/2 - 1 if v[0] ≠ v[j] Question 2 is similar to question 1 (except M and N are reversed), so the answer is - mj/2(n - 1)j/2 - 1 if v[0] = v[j] - mj/2(n - 2)j/2 - 1 if v[0] ≠ v[j] For question 3, assume j is odd and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. There are (j + 1)/2 - 1 vertices having even index, excluding v[0]. There are also (j + 1)/2 - 1 vertices having odd index, excluding v[j]. Hence, the answer to the question is ((m - 1)(n - 1))(j + 1)/2 - 1. Am I correct here?
  13. You'll notice, if/when you take more maths. courses, that maths. books rarely make use of actual numbers. Mathematics isn't only about numbers. Haven't you studied any algorithms in your discrete maths. course?
  14. This is a no no. You can't use the Taylor series expansion because Taylor series are constructed using derivatives and derivatives automatically imply continuity. You destroy the purpose of this exercise by 'omitting' the proof. You're doing it again. Naturally, but if the point is an arbitrary point in the domain of the function in question, then it follows that the function in question is continuous in its domain.
  15. Yes they do repeat infinitely. If the numbers you use contain a finite number of digits, then you are not dealing with the reals, but rather a subset of them.
  16. The lexicographical order definition you give does not order the reals. Here is a simple counter-example: Let [math]\textstyle \alpha[/math] = 1.000... and [math]\textstyle \beta[/math] = 0.999...
  17. I said this because of the explanation you gave me for your equation: " y''=a-ky'/mp this is what i belive...". Don't believe, derive and explain. I didn't use any vector calculus. The equation I gave you is in vector form, but you can easily break it up into components and solve for each individually.
  18. I'll assume that by a you actually mean g (acceleration due to gravity). So you're saying the projectile's acceleration is constant? Why would you believe this? Physics doesn't work that way. The projectile also experiences acceleration in the horizontal direction (due to friction), so if you want a complete description of the projectile's motion, you'll have to deal with this also.
  19. It would be nice if you could explain what you are doing in a little more detail (particularly your first two equations). Anywho...I would approach this problem by first using Netwon's 2. law on the projectile, i.e. ma(t) = mg + f(t) where f(t) is the force of friction. Note that I've written certain terms in bold to indicate they are vectors. You'll have to remember that f(t) not only changes in magnitude but also in direction with time. In the end, you're going to have to solve a pair of diff. equations (which you may or may not know how to solve, given your background).
  20. You need to help us understand what exactly you need help with. Please be specific. Mandrake already did the first question for you. Just follow Mandrake's basic outline to solve the rest of the questions.
  21. I revive this old post in order to resolve the matter in question once and for all. I have conferred this problem with a colleague of mine. He suggested that m and d are both constants, which I certaintly agree on. The misunderstandings came from the wording of the problem (i.e. the problem does not explicitly state that d and m are constants). Here is a similar, albeit harder, ambigous problem: Suppose {a[n]} is an increasing sequence and that whenever m divides n, a[n] = ca[n/m] + d, where c and d are real numbers satisfying c > 1 and d > 0, and m is an integer satisfying m > 1. Show that a[n] = [math]\textstyle \Theta (n^{\log _m c})[/math]. Nowhere does the problem state that c, d, and m are constants, though one must assume this to solve the problem. Here is the solution: Let n = mk so a[n] = a[mk]. Define b[k] = a[mk]. The given recurrence can be written as b[k] = cb[k - 1] + d. "Expanding" the recurrence yields b[k] = ckb[0] + ck - 1d + ck - 2d + ... + cd + d. Simplifing this expression yields a[mk] = b[k] = cka[1] + d(ck - 1)/(c - 1) where a[1] = b[0] (by definition). Since [math]\textstyle c^k = m^{\log _m c^k} = m^{k\log _mc} = n^{\log _m c}[/math] then [math]\textstyle a_{m^k} = \Theta (n^{\log _m c})[/math]. But what happens if n is not a power of m? Algebra says mk - 1 < n ≤ mk so a[mk - 1] < a[n] ≤ a[mk] or ck - 1a[1] + d(ck - 1 - 1)/(c - 1) < a[n] ≤ cka[1] + d(ck - 1)/(c - 1) Concentrating on the left-hand side, one can see that ck - 1a[1] + d(ck - 1 - 1)/(c - 1) ≥ ck - 1 = [math]\frac{1}{c} m^{k \log _m c} \ge \frac{1}{c}n^{\log _m c} = \Omega(n^{\log _m c})[/math] On the right-hand side, one can use algebra and derive cka[1] + d(ck - 1)/(c - 1) = [math]m^{k \log _m c}a_1 +\dots < cn^{\log _m c}a_1 + \dots = O(n^{\log _m c})[/math] Therefore [math]\textdisplay a_n = \Theta(n^{\log _m c})[/math]. What I have essentially proven here is a simpler version of the Master Theorem. The original problem (see first post) is an even simpler version of the Master Theorem. How interesting!
  22. The first question you should be asking yourself is: How do I contruct [math]\textdisplay \nabla ^3[/math]? The biharmonic operator provided in the link by Aeschylus should be written as [math]\textdisplay \nabla ^2 \nabla ^2[/math], not as [math]\textdisplay \nabla ^4[/math] (since that doesn't make any sense, but it apparently is defined that way to shorten the notation). Just remember that these operators are short-hand for large expressions which mathematicians are too lazy to write.
  23. These questions are pretty straight forward. Just show that each relation is reflexive, symmetric and transitive. If you have any specific problems, let us know.
  24. It's been a long time but I think I've figured it out. Let s(n) denote the number of different vertex-labelings of an n-cube. To construct and (n+1)-cube, one combines two n-cubes G and G' by drawing an appropriate edge from a vertex in G to a vertex in G'. In how many ways can this be done? Let v be a vertex in G and v' a vertex in G' with the same label A = a[1] a[2] ... a[n]. Draw and edge from v to v'. Since the labels of v and v' must differ by one bit, one must append an extra bit x to the label of v and ~x to the label of v' in the same relative position. This can be done in n + 1 ways (in front of a[1], in front of a[2], ..., in front of a[n] or behind a[n]). Since x can have on of two values, the answer is 2(n + 1) ways. Do this for every vertex in G and G' with the same label to contruct the (n+1)-cube. Because G can have on of s(n) different vertex-labelings, then the number of different vertex-labelings in the (n+1)-cube is s(n + 1) = 2(n + 1)s(n). Solving this recurrence relations gives [math]\textstyle s(n+1) = 2^{n+1}(n+1)![/math]. Hence, the number of different vertex-labelings for an n-cube is [math]\textstyle 2^{n}(n)![/math].
  25. e(ho0n3

    Stamps problem

    Wait! I'm assuming that a = gcd(m,n). Your proof assumes that gcd(m,n) is the minimum increment. To make your proof valid, you need to prove that the difference between a number S (> P) and P is a multiple of gcd(m,n), i.e. S - P = (k)gcd(m,n) for some integer k > 0.
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.