-   Puzzles (
-   -   Combinatorics (

Kees 2006-04-21 07:58

You have a set of k!+k-1 elements (k>1), numbered 1, 2,..., k!+k-1 .
Let A be the set of subsets with exactly k elements.
Let B be the set of subsets with exactly k-1 elements, which includes also all the permutations of such a subset (so if for instance k=4 then the subsets {1,2,3},{1,3,2},{2,3,1},{2,1,3},{3,1,2}{3,2,1} are all in B.

Evidently #A=#B

Can you construct a bijection f such that f(A_i)=B_i and such that for all i
A_i contains B_i ?

Kees 2006-05-03 11:14

In all honesty, for me it is an open question

jebeagles 2006-05-04 01:02

Given a k-element subset, remove any of the k elements, this clearly is a permutation of k-1 elements.

Take a set (k-1)-element subsets of the same k-1 elements. There are k! remaining elements that can be placed back into the (k-1)-element subsets. Now, there are exactly k repeated k-element subsets doing this process, so there are only (k-1)! that can be added to each set of permutations. Now there are (k-1)! permutations, and (k-1)! elements that can be added to those permutations, adding an element to each permutation out of the possible (k-1)! elements gives a distinct k-element subset.

Therefore, bijection.
is that what you were looking for, or am I off?

Kees 2006-05-09 08:38

At least you are trying for a solution. I wonder however whether I should accept this solution. It seems all right, but it silently assumes the following:
if during the process of 'adding' an element out of the (k-1)! available to one of the (k-1)! permutations we get a k-subset twice, this would mean that another k-subset does not get attributed and we should be able to settle that.

There is yet another snag: for the moment we have only looked at one subset of k-1 elements.There are however quite some subsets of k-1 elements. Are we still getting distinct k-subsets ?

Kees 2006-05-09 11:53

you are right, the second part of my answer is gibberish at best...:redface: :cat:

what jebeagles is showing is the following:

we have the set {1,...,k!+k-1} and we take some subset of k-1 elements.
say {1,...,k-1}.
To this subset we can 'add' k! different elements. Here we have our first problem. The number of sets {1,...,k-1} including permutations is (k-1)!

How to add the remaining elements? (we had k!=(k-1)! * k elements remaining after selecting k-1 elements). So which do we select ? And what happens to the selectionprocedures for other subsets (for instance {1,...,k-2,k}) after this selection. Can we still fill. I am not really satisfied with the answer, actually. All that seems to be shown is that the two sets have the same size (which I offered at the beginning of the problem). If that was the end to it, we would obviously have a bijection. But the extra condition makes this unclear for me.

tom11784 2006-05-12 19:25

If you number the subsets by ranking from least to greatest for first term, then second term, then third term, then fourth
i.e. A1={1,2,3,4} A2={1,2,4,3} A3={1,3,2,4} A4={1,3,4,2} ...

and f({a,b,c,d})={a,b,c}

then B1={1,2,3} B2={1,2,4} B3={1,3,2} B4={1,3,4} ...

which I believe meets your requirements, but I may be reading something incorrectly

Kees 2006-05-13 06:58

The problem is that the subsets in A do not have permutations of themselves

A1=(1,2,3,4), A2=(1,2,3,5)
B1=(1,2,3), B2=(1,3,2)


All times are UTC. The time now is 06:31.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.