Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一种证明方法!

Posted by Bark at 2007-11-26 12:02:50 on Problem 1354
P=2(n-1)!

定义一个环:
              1  2
          n      3
        n-1       4
            ... 5

在这个环上,每个位子上的箱子存放打开下一个箱子的钥匙,1中开2,2中开3,...,n中开1。

     则此题分两种情况讨论:

1 ,A1和A2一起组成一个规模为n的大环。
    即1中开2,2中开3,...,x中开A1,A1中开x+1,...,y中开A2,A2中开y+1,...,n中开1
    则有A(2,n)=n(n-1)种放法将A1和A2放入上图的环中,再由于圆环中不存在绝对位置,是个圆排列,还要除以n,n(n-1)/n=n-1,剩下的n-2个位置则按照环的定义有(n-2)!种放法。
      
       故P1=(n-1)*(n-2)!=(n-1)! 

2 ,A1和A2分别形成两个独立的小环,其规模分别为x,y. 则 x+y=n && x,y>=1
    当x=1时,即为A1中存放打开A1的钥匙。
    对于有A1的小环,只要确定该环中最后一个箱子存放打开A1的钥匙
    同理于有A2的小环。
    剩下的n-2个位置则按照环的定义放入箱子,有(n-2)!种放法。
    方程 x+y=n && x,y>=1 的解的组数为n-1
 
       故P2=(n-1)*(n-2)!=(n-1)!

     所以总方案数 P=(n-1)!+(n-1)!=2(n-1)!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator