Emil the Mathematician
Emil is trying to PROVE that if you consider a set of size 2n+1, you can cycle through all the subsets of size n or n+1, by adding or deleting one element at a time.
Can you help Emil? ... he's a little senile and eccentric!
Can you help Emil? ... he's a little senile and eccentric!
posted by Zaux at
10:08 PM
11 Comments:
Please clarify. Do you mean first create a set of size n and another of size n+1 then start swapping a pair of elements (one from each set) between the two sets?
... if my interpretation is correct, then if n = 0, it can't be done as one of the sets is empty, so there is nothing to swap with.
If n = 1, then let starting sets be {a} and {b,c} then can do a<->b => {b}, {a,c} then b<->c => {c} and {a,b}. So that can be done.
Seems pretty obvious that one could associate all the elements of the smaller set with a subset of the larger set, and exchange the whole lot (in any order), then simply start again but exclude a different element of the larger set and repeat the whole process. Keep on going through the larger set but exluding a different element each time.
Not exactly a quality maths argument, but I'm pretty sure that Emil is right for n > 0.
There again, I've probably misunderstood the question.
Chris ... it's not prove-able. Just a fun consideration. You guys were solving everything so quickly, I posted it simply to see the reponses ...
I am confused, but if as set has 2n+1 elements, then the number of elements is an odd number.
If the set has 23 elements, you can cast out one or add one to then have 22 or 24, but then the set size is not an odd number anymore. But if n can be a fraction, then it might work, but can you have half and element?
Hi Ragknot. LOL you certainly are confused, and you're not alone.
I was very suspicious that Zaux had made this one up - and judging by the post he half an hour ago, I think I'm right.
I'm pretty sure that I've given a half decent "proof" of what I guess the problem was. I didn't go overboard because of my suspicions.
I expect that higher maths might allow half an element (don't ask me what that might mean though), but there is no need to go that far. "Higher" maths allows for half a derivative say. If you're curious, take a glance here: http://en.wikipedia.org/wiki/Fractional_calculus.
I did not fabricate this one ... came from a math source and as I stated was identidied as un-proveable. I posted it mostly for curiosity to see howe it would be approached.
Hi Zaux. Clearly I haven't understood the problem. My interpretation seems to have an almost trivial affirmative proof.
Would you post an illustration of what is meant by the question?
Chris ... sorry, don't have much more info on this. It was presented as a problem which has been pondered by many well known mathematicians. As I said, the problems were being solves so quickly, I thought it would give many of you who are good mathematicians something to ponder.
Many believe there is a pattern that will work for any n. No one seems to believe it false, but no one has proved it. (I don't understand some of this ... but) Computer experiments have suggested that the number of ways to cycle through the middle levels is an extremely rapidly increasing function of n. That it would drop to 0 for some n seems highly implausible, but no proof to the contrary exists.
Now ... I hope some of you understood that ... I do not ... heh heh.
As I said, it was posted as a curiosity to see the response.
Hi Zaux. If you can write a program, then you must have a clear idea of what the question is asking, I haven't.
Is there a large financial reward for cracking it?
To my knowledge, no reward for cracking it ... let's move on ...
Rats, I could do with the loot to pay my $480 bar bill.
Post a Comment
Links to this post:
Create a Link
<< Home