Sorry but thats a repeated one!
Is difficult to read all the 680 posts and remember all the questions.
The answer is:
413213
Printable View
Sorry but thats a repeated one!
Is difficult to read all the 680 posts and remember all the questions.
The answer is:
413213
I'm too lazy to make one up myself, so I found another
A man walks up to you and says - "everything I say to you is a lie."
Is he telling you the truth or is he lying?
Or you can go Doctor Luz since you answered first.
Is not true neither false. Is a contradiction.
If he is telling the truth he lies, then he is not telling the thruth
if he is liying then he has told the truth, then he is not liying, and so on ad infinitum.
I'm lazy today too.
Here is an old one.
How would you join all the picture points whith only 4 straight lines without leaving the pen from the paper?
hmm... Do you mean to ask: Can it be done with four lines?
Seems to me the answer is no.
let
f(line) = the number of points covered by a line and not by any of the previously drawn lines.
clearly only one of the lines can have f(line) = 3. Since you can not lift the pencil at least one endpoint of two consecutively drawn lines must coincide.
I claim that f(line) = 1 for one of the four lines
Suppose Not
then three of the lines have f(line) = 2 and and one line has f(line)=3.
If not then f(line)= 2 for all of the lines and so does not cover 9 points.
The only way a line can have f(line) = 3 is to be the first line and since the next line drawn has f(line) = 2, this first line must draw from a corner to a corner.
now since the next line has f(line) = 2 and starts at a corner it also must draw form a corner to a corner.
and repeat, since the third line has f(line) = 2 and starts at a corner it must draw to the last available corner.
since the forth line starts at a corner and has f(line)=2. it also must draw to a corner, but all corners have already been covered
contradiction.
so at least one line has f(line)=1 so you can not cover 9 points shown with four lines
Quote:
Originally posted by Goodz13
What row of numbers comes next?
1
11
21
1211
111221
312211
13112221
Wait a sec... shouldn't it be 1113213211?Quote:
Originally posted by Doctor Luz
The answer is: 413213
I will attempt to draw this without using a picture:Quote:
Originally posted by Doctor Luz
How would you join all the picture points whith only 4 straight lines without leaving the pen from the paper?
I hope you can understand that ... ;)Code:_._._.
\. ./.
.X. !
\|
well of course you can do it if the lines are not required to begin and end at one of the points in the grid. That can't be the question because there is no challenge in it. Please clarify Dr. Luz.
well, I take it back, I guess the challenge was to see that you could terminate outside the grid. Assuming this is what was meant by the question
hehe... that's right, cover up the mistake... or just delete the post... ;)Quote:
Originally posted by souldog
well of course you can do it if the lines are not required to begin and end at one of the points in the grid. That can't be the question because there is no challenge in it. Please clarify Dr. Luz.
well, I take it back, I guess the challenge was to see that you could terminate outside the grid. Assuming this is what was meant by the question
Really the solution is that posted by solarflare.
Sorry if I have not been clear. I did not told that there is not any restriction about finishing the lines in the grid points.
Well there is no shame in being wrong, so why would I delete the post?Quote:
Originally posted by solarflare
hehe... that's right, cover up the mistake... or just delete the post... ;)
OK.. I would like to be able to ask a couple of questions in succession. They are simple questions and the result is nice.
I will include all the definitions needed
DEFINITIONS:
Given a set V and a set C of functions between subsets of V,
where V is the union of the domains and ranges of elements of C,
define a graph G(V,C)= {<x,y,c>| x, y are in V, c is in C and c(x) = y}
Elements of V are called vertices while elements of G(V,C) are called edges. given an edge e= <x,y,c> x is the first vertex, y is the second vertex and c is the color of e.
If X =The union of the domains of elements of C is disjoint from Y =the union of the ranges of elements of C then the graph is called a bipartite graph and is denoted B(X,Y,C)
Finally if the elements of C generate a group acting on V, then G(V,C) is called a cayley graph. and is denoted Gc(V)
Here a group G is said to act on a set V if each g in G corresponds to a permutation of V, for all g, h in G and x in V g(h(x)) = (gh)(x) and the identity of G is the identity permutation. The group G is said to act without non-trivial fixed point if no non-identity element of G fixes an element of V. if g(x)=x iff g = e the identity.
Two distinct edges of a graph are adjacent if they share a vertex and two vertices are adjacent if they are elements of a single edge. The valency of a vertex v is the cardinality of the set of vertices adjacent to it and the degree of a vertex is the cardinality of the set of edges containing it.
A path P=P(e1,...en) in a graph is a sequence of distinct edges e1...en, where for each i = 1,...,n-1 edge i is adjacent to edge i+1. and no vertex of P is contianed in more than two edges of P. note the following is a path p = {<x,y,c>, <x,z,c'>} i.e. a path can start in the range. Given a path p(e1,...,en) with e1=<x,y,c> and en=<z,w,c'>, if y is a vertex of e2 then P starts at x, otherwise it starts at y. If z is a vertex of edge n-1 then P ends at w, otherwise it ends at z. A path which starts at x' and ends at w' is said to connect x' to w'. P is called a cycle when it start at x', ends at w' and x'=w'. By convention any vertex x is connected to itself by a path of length 0.
Clearly the property of being connected defines an equivalence on the vertices of G(V,C) and restricting the functions in C to an equivalence class yields a subgraph of G (By these definitions a subgraph is just a subset) called a connected component. Any two distinct connected components are disjoint. Define the path-distance between two vertices x and y of a connected component by min{length(P), P connects x to y}. Note that path-distance defines a integer valued metric on a connected component.
A subset I of a bipartite graph B = B(X, Y, C) is called a matching if distinct elements of I are not adjacent. A vertex v of the graph B iis said to be covered by the matching I if it is in some and so exactly one element of I. A perfect matching is one which covers all elements of B.
END OF DEFINITIONS
Prove the following
Lemma: Let B(X,Y,C) be a bipartite graph. If the valency of each vertex of B is at least two and each connected component of B contains at most one cycle, then B contains a perfect matching.
I must say, souldog, that if questions in college had been this interesting, I would have done my homework more often! It is one of the smoothest, quickest, tightest introductions into the connection between homology and graph theory (and expressly forming the graph theory on function theory!). Although this is a great foundation to start learning either graph theory or homology, I must say I have never seen a book with that form...
Anyway, for the solution I would begin with a lemma from homology: a path P with no loops has a boundary d(P) that consists of at least 2 points with a valency of less than or equal to 1. Its a simple inductive proof on paths with no self-interception inducted over path length.
Now, you only have to look at each component, since a perfect matching for each connected component gives a perfect matching forthe entire graph through union (since there are no connections by definition between distinct connected components).
The key is that for each vertex with at least two valence, we can arbitrarily distinguish 2 edges as "in" and "out" with repect to that vertex (ie. we can direct two edges relative to each vertex). We look at the X and Y components of the bipartite graph and choose an arbitrary element of X which we label x1 (by the theorem of choice -- the finite version of the axiom of choice -- because we want to enumerate an ordering on the sets X and Y). Construct a path P from x1 by the following rule: after a choice of in and out directings on x1 has made, choose the edge out as the next element of the path. Following this procedure, you label the vertices reached y1, x2, y2, ... until the path forms a cycle and an edge contains a previously used vertex. We know that each connected component must have at least one loop by the lemma and the knowledge that there exist no valence 1 vertices. If the subsets of X and Y contained in the path that has looped upon itself (call the subsets xx and yy) are not the entire sets X and Y then we look at X disjoint xx and Y disjoint yy and build a new path until it loops or a vertex is constricted (its out must go to a vertex of other path). The same is done backwards for the in to the first vertex, and we arrive at one of two situations: either both in and out connect to the first path or a second loop is formed separate from the first loop. In the first case we also have a new loop separate from the initial loop, since the path separating the vertices in and out connect two disjoint paths (and thus a loop). Thus there is a contradiction and you have proved that all vertices of X are in xx and all of Y in yy.
So finally, you just look at the subset of the path that connects the "out"s only from X's to Y's (x1 out to y1, x2 out to y2). This is a matching (no adjacent edges) and the contradiction above proves it is perfect. You also get a nice relationship on the fact that the bipartite graph must have equal cardinality Xs and Ys if it is to have all vertices valence 2 or greater yet only one loop. As mentioned above the union of all the perfect matchings in each component gives the perfect matching for the graph.
This formulation of graph thoery was worked out by my twin brother and I. I really like it beacuse all the various structures you usually consider are just subsets of the original graph.
I don't think your proof quite works. There is no assumption that the cardinality of the connected components is finite. In particular there may be connected components which contain no cycles.
It is a very slick proof of the finite case. Maybe I have misunderstood something?
I must admit I had you in mind Galathaea when I asked this question. I hope you keep working on it, I think you will like where it goes next...
Aha! Infinity, my long time friend and sometimes enemy... I will have to have a talk with her...
Ah.. now that I am back at work, I have more time to think about this little bugger :)! I'll just post some of my random thoughts since I find if I commit my thoughts to public perusal, my brain works a bit harder at working things out...
Ok. So the loss of the assumption of finite graphs makes use of the lemma unworkable. There are infinite paths (and indeed many infinite trees - those with nonterminating leaves) with no cycles and yet at least 2 valence at each vertex (the boundary of these graphs can indeed be empty). So the proof of the infinite case will probably require the use of the Axiom of Choice and construction of a possibly infinite series of cases of paths. Basically, one will probably have to use transfinite induction to show that there must be for every infinite path at least one valence 3 vertex connecting it to another path (or it would fail to be part of the connected component - a contradiction) -- but wait... that might not even be necessary. Once on has an inductive construction of paths (finite or infinite), one should be able to construct a matching in the same way as above (extending now both directions down the path if necessary). It seems that the matching over non-terminating leaves won't cause a problem with the previous construction, but I am still thinking mainly in terms of a countable selection of vertices. I guess if there were an uncountable number of vertices, the transfinite induction would still work (call a path constructed from a given choice vertex a "neighborhood" of the vertex -- then look at the case of the graph minus the path and prove each vertex still has matching element possible). Hmm... maybe the use of the idea that if a path does not include all points implies that there are at least two vertices of valence 3 is important here...
Well, it is indeed more interesting still. I will work on ironing out the ideas for a formal proof. It seems that most of the machinery from the finite proof could be gotten rid of once the infinite proof is worked out, since the lemma was too important there...
If anyone sees something terribly awry in my musings, please let me know!
Paths are always finite in length. In particular lets say that the connected components are either finite or countable. I guess we could start talking about other cases and Transfinite Induction would proably work (what to do at limit cardinals?), but is not needed.
Yes, but you really don't need to proceed by contradiction. What to do about a connected component with a cycle?Quote:
Once on has an inductive construction of paths (finite or infinite), one should be able to construct a matching in the same way as above (extending now both directions down the path if necessary). It seems that the matching over non-terminating leaves won't cause a problem with the previous construction, but I am still thinking mainly in terms of a countable selection of vertices. I guess if there were an uncountable number of vertices, the transfinite induction would still work (call a path constructed from a given choice vertex a "neighborhood" of the vertex -- then look at the case of the graph minus the path and prove each vertex still has matching element possible). Hmm... maybe the use of the idea that if a path does not include all points implies that there are at least two vertices of valence 3 is important here...