Solving Axiom SystemsDate: 02/11/2003 at 12:59:08 From: Jen Subject: Solving axiom systems Axiom 1. Any two distinct students belong to exactly two clubs in common. Axiom 2. There exist at least two students. Axiom 3. For each club, there exists at most one student who doesn't belong to it. Axiom 4. Each student belongs to exactly four clubs. Theorem 1. There exist exactly six clubs. Theorem 2. At least one student belongs to each club. Theorem 3. For each student, there exist exactly two clubs to which he does not belong. I have to prove the theorems with the axioms and I have no idea how to do it. Date: 02/16/2003 at 05:32:37 From: Doctor Jacques Subject: Re: Solving axiom systems Hi Jen, We will prove theorem 1 in two steps: Lemma 1.1 : there are at least 6 clubs By A.2, there are at least two students. The first student is a member of 4 clubs (A.4). By A.1, the second student is a member of exactly two of these clubs. As he is a member of 4 clubs (A.2), there must be at least two other clubs. Lemma 1.2 : there are at most 6 clubs. Assume by contradiction that there are at least 7 clubs. Pick one student (A.2 allows this), and call it "a". Number the clubs from 1 to n (n >= 7), in such a way that "a" is a member of clubs 1 through 4 and no other club (A.4). As "a" is not a member of clubs 5, 6, and 7, every student other than "a" (there is at least one such student, by A.2) is a member of these clubs (A.3). Each of these other students must share two clubs with "a" (A.1), and thus be a member of two clubs in the set {1..4}. This makes each such student a member of at least 5 clubs, which contradicts A.4 Theorem 1 follows then from these two lemmas. Theorem 2 is a consequence of A.2 and A.3 - I'll let you show that. Theorem 3 follows immediately from Theorem 1 and A.4 - I'll let you show it too. Extra credit ------------ Can you show that there are at most three students ? A possible course of attack would be: Assume that there are s students. Make a rectangular (s*6) table, where rows correspond to students and columns correspond to clubs. Put a mark in each square for which the student belongs to the club, and estimate the number of marks in two different ways (by row first or by column first). Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/