- mathfun@mailman.xmission.com - mailman.xmission.com

Re: [math-fun] Cardinality puzzle - answer
by dasimov＠earthlink.net 10 Mar '06

10 Mar '06

Franklin wrote: << Here's a related problem. Can you describe a *maximal* uncountable antichain? >> << More difficult: describe an (uncountable) maximal antichain where every set is infinite. (I don't know the answer to this second question. It might be: no, no such description is possible.) >> The antichain A = { Z - {n} : n is in Z} is maximal and contains only infinite sets: (Any other proper subset of Z must be missing at least 2 integers m and n, so is a proper subset of Z - {n}, so cannot be added to A -- and of course Z can't either. ) << [Gareth wrote:] >. . . Next: what's the largest a *chain* [of subsets of Z] can be? Obviously aleph-nought. At least one integer must be added at each step. >> There is a subtle flaw in the argument here, which is why this is such a great puzzle. --Dan

3 2

[math-fun] Cardinality puzzle
by dasimov＠earthlink.net 09 Mar '06

09 Mar '06

Let a collection C of subsets of the integers be called an "antichain" if there exists no pair of sets X,Y in C such that X is a subset of Y. Puzzle: What is the largest cardinality that an antichain can have? --Dan

3 3

[math-fun] Cardinality non-puzzle
by dasimov＠earthlink.net 09 Mar '06

09 Mar '06

Okay, now I'm wondering if a set of S any cardinality K > aleph_0 has standard formulas for the maximum cardinality C(K) of a chain of its subsets, and A(K) of an antichain of its subsets. For finite K: * C(K) is clearly K+1. * The non-obvious formula for A(K) is given by Sperner's Theorem. There's a nice discussion and short proof of it in "Proofs from The Book", 2nd ed. (there is a 3rd). But you may enjoy thinking about it before reading about it. --Dan

1 0

[math-fun] Kimberlike sequences (for k=2 to k=9)
by Eric Angelini 09 Mar '06

09 Mar '06

Computed by Gilles Sadowski : http://www.cetteadressecomportecinquantesignes.com/Kimberlike02.htm Looks like, yes, it is always possible to fill the "holes"... [Can't see any pattern, though] Best, É. (and a special thanks to Paul for his interesting private mail)

1 0

RE: [math-fun] sudoku, uniqueness, proofs
by Cordwell, William R 08 Mar '06

08 Mar '06

-----Original Message----- From: math-fun-bounces+cordwell=sandia.gov(a)mailman.xmission.com [mailto:math-fun-bounces+cordwell=sandia.gov@mailman.xmission.com]On Behalf Of Gary McGuire Sent: Wednesday, March 08, 2006 5:24 AM To: math-fun Subject: Re: [math-fun] sudoku, uniqueness, proofs Michael Kleber wrote: [deleted part] Dan wrote: >Are you sure that such solutions *are* given full credit in Putnam exams and >Olympiads? I don't know if that's the case. No, I'm not sure. I thought there would be some readers of this group who know. I know this particular problem is easy to solve the other way, but I've seen tricky problems which are made much easier by reasoning "here I am sitting in a Putnam/whatever, therefore this problem has a nice solution, therefore....." [deleted part] Gary McGuire _______________________________________________ I coach a MathCounts (grades 6-8) team, as well as high school students preparing for various contests. On many of the lower-level contests (say, MathCounts or the AMC->12 and the AIME), the exam only asks for the answer. In this case, I think that noticing, say, that a problem doesn't seem to have enough information, and fixing an apparently arbitrary value that will allow one to easily solve the problem (within the logical constraints) falls under a mixture of math and test-taking skills. For the AMC->12, many of the kids are, in ability, close to making the cutoff (a score of 100) for qualifying for the American Invitational (AIME), so I also have them work out the strategy for how many questions they should answer in certain situations. The AMC scores the 25-question exam by giving 6 points for each correct answer (multiple choice), 2.5 points for each unanswered problem, and 0 for each incorrect problem. If one's goal is to attain a score of >= 100, then, there's no advantage in answering 12 questions vs. 11 questions (and a possible disadvantage), but one needs to answer at least 11 questions. Qualifying for the AIME is not a zero-sum game, so I think that it is reasonable to point out this strategy to the kids. By the time that they reach the USAMO, they will be writing proofs for the problems; I've not graded those exams, but I would be surprised if a student got full credit for assuming that a solution was unique as part of his proof, unless he could show it later. Philosophically, I admit to being bothered when, say, a basketball team is in the lead and it intentionally delays, to deny the other team a chance at winning. I understand that this is within the rules, but it bugs me. I don't see the above strategies in that light, as one is not denying his competitors the same chance. However, I would not categorize using the strategies as "being better at math". --Bill Cordwell

1 0

[math-fun] Kimberlike sequences
by Eric Angelini 08 Mar '06

08 Mar '06

Hello Seqfan and Math-fun, please have a look there, if you have a couple of minutes: http://www.cetteadressecomportecinquantesignes.com/Kimberlike01.htm Best, É.

2 1

[math-fun] RE: Kimberlike sequences
by Eric Angelini 08 Mar '06

08 Mar '06

[Paul] : > Perhaps a deeper look at the hidden structure beneath Clark Kimberling's sequences will shed light on yours. ... thank you, Paul, for this interesting post -- and no, I had never heard before about Beatty sequences. I will plunge asap into this matter and try to see if it can be of any help in answering my questions. Thanks again -- and especially for this: > Here is how to determine the parameter r of the Beatty sequences > from the distance factor d. > The r is a root of quadratic equation 1 - d*x - x^2 = 0, or > r=(sqrt(d^2+4)-d)/2. ... Very interesting ! Best, É.

1 0

Re: [math-fun] Re: proofs
by dasimov＠earthlink.net 08 Mar '06

08 Mar '06

Apropos proof-checking by any means: In Fall, 2002, the Russian mathematician Grigori Perelman posted to the math ArXiv website some papers claiming to prove W. Thurston's geometrization conjecture (TGC) <http://en.wikipedia.org/wiki/Geometrization_conjecture>. If true, TGC would greatly advance the field of 3-manifolds, and would also imply the famous so-called Poincare conjecture (PC) as well (one of the seven Clay $10^6 prize problems). Since then Perelman has given detailed lecture series at a number of U.S. math departments, and undoubtedly many others around the world. Ever so slowly, the experts in this field seem to be concluding cautiously that at least the part of Perelman's work that purports to prove the PC is *probably true. They're less sure about the entire TGC. (I believe there is at least one piece of the TGC proof that Perelman has promised to post on the ArXiv, but has not yet done so.) In March, 2004, Scientific American published an article that stated that PC had been proved by Perelman. Everyone I asked who attended any of his lectures expressed cautious optimism for PC, but none would affirm that it had been proven. That October, John Morgan of Columbia published an article written in August, 2004 that discussed Perelman's work, but he dd not affirm that the proof was correct. Though the optimism is slowly increasing for PC, it still seems no one among the experts is ready to publicly affirm that PC has been proven. For me this is a bit like watching a drama of high suspense unfold in slow motion. Assuming the absence of reliable automated theorem-checkers for this kind of proof, how do we decide when Perelman's work is correct? (Incidentally, he has apparently never submitted it to a peer-reviewed journal, but some sources say it's already gotten much more careful scrutiny than most such submissions would.) --Dan _________________________________ * Poincare didn't actually phrase this as a conjecture; he asked whether or not it was true.

5 6

[math-fun] Re: Kimberlike sequences
by Paul D. Hanna 07 Mar '06

07 Mar '06

Eric (and Seqfans), > please have a look there, if you have a couple of minutes: > http://www.cetteadressecomportecinquantesignes.com/Kimberlike01.htm > Best, > Ã. Your generalization is curious. Perhaps a deeper look at the hidden structure beneath Clark Kimberling's sequences will shed light on yours. Consider Kimberling's sequences A026242 and A026249 in particular. In these, every n occurs twice, at 'distance factors' 1 (A026242) and 2 (A026249). In A026242, the distance between positions where the 2 n's occur is 1*n; in A026249, the distance between positions where the 2 n's occur is 2*n. As you know, these can be constructed from complementary Beatty sequences. The distance factor, if it exists, is determined by the parameter used in the Beatty sequences. Here is how to determine the parameter r of the Beatty sequences from the distance factor d. The r is a root of quadratic equation 1 - d*x - x^2 = 0, or r=(sqrt(d^2+4)-d)/2. distance; r=root ; equation ; Sequence# d=1; r=(sqrt(5)-1)/2 ; 1-x-x^2 = 0 ; A026242 d=2; r=sqrt(2)-1 ; 1-2*x-x^2 = 0 ; A026249 d=3; r=(sqrt(13)-3)/2; 1-3*x-x^2 = 0 ; NOT IN OEIS d=4; r=sqrt(5)-2 ; 1-4*x-x^2 = 0 ; NOT IN OEIS >From r, we generate the Lower and Upper complementary Beatty sequences. Then the integer n will occur at postions L(n) and U(n) in the sequence. r=(sqrt(d^2+4)-d)/2 L(n)=floor(n*(1+r)) /* Lower Beatty seq */ U(n)=floor(n*(1+1/r)) /* Upper Beatty seq */ A=vector(U(100)); for(n=1,100,A[L(n)]=n;A[U(n)]=n) Here are some examples for d=3, and d=4. Distance factor d=3; r=(sqrt(13)-3)/2; NOT IN OEIS 1,2,3,1,4,5,6,2,7,8,9,3,10,11,12,13,4,14,15,16,5,17,18,19,6, 20,21,22,23,7,24,25,26,8,27,28,29,9,30,31,32,33,10,34,35,36, 11,37,38,39,12,40,41,42,13,43,44,45,46,14,47,48,49,15,50,51, 52,16,53,54,55,56,17,57,58,59,18,60,61,62,19,63,64,65,66,20, 67,68,69,21,70,71,72,22,73,74,75,23,76,77,78,79,24,80,81,82, 25,83,84,85,26,86,87,88,89,27,90,91,92,28, Distance factor d=4; r=sqrt(5)-2; NOT IN OEIS 1,2,3,4,1,5,6,7,8,2,9,10,11,12,3,13,14,15,16,4,17,18,19,20, 21,5,22,23,24,25,6,26,27,28,29,7,30,31,32,33,8,34,35,36,37, 38,9,39,40,41,42,10,43,44,45,46,11,47,48,49,50,12,51,52,53, 54,55,13,56,57,58,59,14,60,61,62,63,15,64,65,66,67,16,68,69, 70,71,72,17,73,74,75,76,18,77,78,79,80,19,81,82,83,84,20,85, 86,87,88,21,89,90,91,92,93,22,94,95,96,97,23, Now, for your case, where you choose every integer n to occur 3 times, perhaps the sequence could be generated using something akin to Beatty sequences. But there would have to be 3 complementary sequences generated from irrational parameter(s). And maybe these parameters would be roots to some cubic equation? These are just surmisings, but what I am attempting to do is find a way of easily generating your sequences similar to the Beatty sequence method. Unfortunately, I do not know of an analogue to Beatty Theorem that will generate 3 complementary sequences! That would be nice ... 'Nough Said, Paul

1 0

RE: [math-fun] sudoku, uniqueness, proofs
by Cordwell, William R 07 Mar '06

07 Mar '06

Is there a good program for drawing geometric figures, such as ellipses and hyperbolas; in particular, I'd like to type in the equations, and have it generate a picture that I can save as a bmp file. Once I have a bmp file, I can use Acrobat to generate a pdf, then use that in LaTex. --Bill C. -----Original Message----- From: math-fun-bounces+cordwell=sandia.gov(a)mailman.xmission.com [mailto:math-fun-bounces+cordwell=sandia.gov@mailman.xmission.com]On Behalf Of Fred lunnon Sent: Tuesday, March 07, 2006 10:59 AM To: math-fun Subject: Re: [math-fun] sudoku, uniqueness, proofs On 3/7/06, Henry Baker <hbaker1(a)pipeline.com> wrote: > The basic idea is to reverse the logic of Tarski's decision procedure for > geometry, which converts geometry into analytic geometry. Since the mapping > is obviously not 1-1, you need a clever way to map questions about polynomials > back into questions about lines, planes, circles, etc. I skimmed over Gary's proof (literally for 2 seconds) and was unable to follow it; then pictured the problem mentally, saw the solution immediately, skimmed the proof again and realised it was saying the same thing as I had pictured. Pondering this chain of events, I wondered how does one teach people to think geometrically like this in the first place? [And when that's out of the way, is there a decent way to get 2-D or 3-D geometrical diagrams into TeX yet?] Fred Lunnon _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

4 3