PoorEnglish's blog

By PoorEnglish, 8 years ago, In English,

http://acm.hdu.edu.cn/showproblem.php?pid=4061

Description

There are N cards on the table, whose front side is written one integer number from 1 to M. We call one card "a type k card" if its number is k. The quantity of type i cards is a_i. 

Let's play a game with these cards. We divide these cards into M piles by random with the only constrains that the quantity of cards in i-th (indexed from 1) pile must exactly be a_i. The possibility of each card appears in i-th pile is directly proportional to the size of this pile. That is to say, if the size of a pile is A, the possibility for each card appears in this pile is A/N assuming that N is the amount of all cards. We choose pile 1 to start the game. Assuming the we now play this game at pile k, we randomly choose a card from pile k with the same possibility for all cards in it, remember the number written on this card and throw it away. If the number on the chosen card is j, we continue this game at pile j on next round. The game terminates when we are going to get a card from an empty pile.

Now the question is, when the game ends, what is the possibility that all piles are empty?

the answer is quite simple (a1/∑ai), here is my idea(not a solution, just some notes)

   If there is a type i card in j-th pile, assign a directed edge from j-th vertex to i-th vertex(i-th vertex denotes i-th pile and there is n vertices in total, of course).We go from the first vertex, and choose an unvisited edge (if any) randomly to visit the next vertex, and the game ends with all piles empty if and only if we traverse the graph by an Eulerian trails(by an Eulerian circuit indeed, since the degree of any vertex is even).

   That is to say, generate the graph randomly, choose an unvisited edge to go randomly, and what’s is the possibility we leave with a Eulerian circuit?

   Take a example to illustrate my idea:

   Two piles, one type 1 card, two type 2 cards.

   There is three graphs in total(a permutations of multiset{1,2,2},3!/(1!*2!)=3):


1|22 - only one way to traverse the graph(note that we must go from the first vertex),and the number of the Eulerian circuit is 0.


2|12 two ways to traverse (1->2->1, 1->2->2->1),and one is the Eulerian circuits.


2|21 it’s the same..

So the possibility is 1/3*(0/1+1/2+1/2)=1/3.

   

    If a pile with n cards, there are n edges to go into the pile and n edges to leave. I pre-determined that if I go from the i-th edges, I must leave from the j-th edge, then I can divide a pile with n cards into n piles with only one card(and with the pair of predetermined edges).

->

(divide the 2-th pile into 2 piles with pre-determined edge.)

There is a1!*a2!...*an!(ai denotes the number of the cards in i-th pile)ways in total to pre-determine, and after the division we get Sc!(Sc=ai) graphs. Considering another instance with Sc piles(one card a pile)of this problem, there is a bijection with these two instance.

to prove this: 

Consider a permutation(of a group) of a multiset(and it's the way of generate the graphs):

(assigning index is to pre-determining the edges indeed)

In this way, we can see these pre-determined graphs covers all the possible ways of edges assigning (Sc! different ways in total).

So the problem is isomorphism with Sc piles with only one card’s. It’s trivial to see the answer is (n-1)! ways to go from any vertex to traverse the graph with a eulerian circuit(a simple combinatorics problem,it is also the number of n-cycle permutations in Sn).

There is a1 vertices in total, so it’s a1*(n-1)!/n!.

----

I know it is very ambiguous...Part of the problem is my poor English,and the other part is I just understand the problem not well.

any one has a better idea?


 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

8 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I can feel the isomorphism somehow, but I can't prove it...

how about this:

let the card with the same type be distinguishable, and assign the predetermined edge to the card(according to the index of the card).by this way, any trail in the original graph has a corresponding trail in Sc piles with only one card.

  • 8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    That is what I want to say...But how to prove it clearly with math?