Messy

Ramsey 定理

发表于 |

Ramsey定理

定理描述

Ramsey定理要解决的是如下问题：
如何正确剥皮
要找这样一个最小的数n，使得 n 个人中必定有 k 个人相识或 l 个人互不相识。

再稍微详细一点的描述是，对于一个完全图Kn，用红蓝两种颜色对每条边染色，每条边只取其中一种颜色，那么n至少要多少，才能使得其中必定有以下两种情况中的至少一种发生：

  1. 含有：所有边都是红色边的，有k个顶点的子图。
  2. 含有：所有边都是蓝色边的，有l个顶点的子图。

这样的n可以由k和l确定，表述为n = R(k,l)。
Ramsey证明，对与给定的正整数数k及l，R(k,l)的答案是唯一和有限的。

关于R(3,3)=6的小问题

题目描述：

证明：6个人中至少存在3个人相互认识或者相互不认识

证明思路：

考虑第一个人A，其余5个人分为两类

  • F = 与第一个人相互认识
  • S = 与第一个人相互不认识
    则其中至少有一类有3个成员。
    若类F有3个成员，则他们或者相互不认识，或者至少有一对P ,Q相互认识，后面一种情况时P ,Q加上第一个人A就构成3个人相互认识。
    否则，类S有3个成员，他们或者互相认识，或者至少有一对L,M相互不认识，后面一种情况时L,M加上第一个人A就构成3个人相互不认识。

HDU 5917 - Instability

2016 ACM-ICPC 长春赛区
传送门

题意：

给定n个点，m条边，然后选择一个点集S，如果里面有一个至少有3个顶点的子集A，A里面的点都不相连，或者都相连，则这个点集S不稳定。
求这样的不稳定的S的个数。

解题思路：

根据Ramsey定理，当S含有6个顶点或者更多的时候，其中必定至少含有一个3个顶点互相相连或者都不相连的子集。
所以要考虑的是顶点数为3,4,5的子集。这部分暴力求解即可。
对于n>=6时的子集个数，运用二项式定理求解：

矬的要死的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 1000000007
using namespace std;
bool mp[110][110];
long long ans = 0;
int m, n;
long long qmul(long long a,long long b){
    long long ret = 1;
    long long tmp = a;
    while(b){
        if (b & 0x1) ret = ret * tmp % MOD;
        tmp = tmp * tmp % MOD;
        b>>=1;
    }
    return ret;
}
int Three(int a, int b, int c){
    if (mp[a][b] && mp[a][c] && mp[b][c]) {
        return true;
    }
    if (!mp[a][b] && !mp[a][c] && !mp[b][c]) {
        return true;
    }
    return false;
}
int Four(int a, int b, int c, int d){
    if (Three(a, b, c) || Three(a, b, d) || Three(a, c, d) || Three(b, c, d)) {
        return true;
    }
    return false;
}
int Five(int a, int b, int c, int d, int e){
    if (Four(a, b, c, d) || Four(a, b, c, e) || Four(a, b, d, e)
        || Four(a, d, c, e) || Four(b, c, d, e)) {
        return true;
    }
    return false;
}
int main(){
    int T, u, v;
    cin >> T;
    for (int Cas = 1; Cas <= T; ++Cas) {
        memset(mp, 0, sizeof(mp));
        cin >> n >> m;
        ans = 0;
        for (int i = 0 ; i < m; ++i) {
            cin >> u >> v;
            mp[u][v] = mp[v][u] = 1;
        }
        for (int i1 = 1; i1 <= n; ++i1) {
            for (int i2 = i1 + 1; i2 <= n; ++i2) {
                for (int i3 = i2 + 1; i3 <= n; ++i3) {
                    if (Three(i1, i2, i3)) {
                        ans++;
                        ans %= MOD;
                    }
                }
            }
        }
        for (int i1 = 1; i1 <= n; ++i1) {
            for (int i2 = i1 + 1; i2 <= n; ++i2) {
                for (int i3 = i2 + 1; i3 <= n; ++i3) {
                    for (int i4 = i3 + 1; i4 <= n; ++i4) {
                        if (Four(i1, i2, i3, i4)) {
                            ans++;
                            ans %= MOD;
                        }
                    }
                }
            }
        }
        for (int i1 = 1; i1 <= n; ++i1) {
            for (int i2 = i1 + 1; i2 <= n; ++i2) {
                for (int i3 = i2 + 1; i3 <= n; ++i3) {
                    for (int i4 = i3 + 1; i4 <= n; ++i4) {
                        for (int i5 = i4 + 1; i5 <= n ; ++i5) {
                            if (Five(i1, i2, i3, i4, i5)) {
                                ans++;
                                ans %= MOD;
                            }
                        }
                    }
                }
            }
        }
        if (n >= 6) {
            ans += qmul(2, n) - 1;
            ans %= MOD;
            ans -= n; ans %= MOD;
            ans -= n * (n - 1) / 2 - MOD; ans %= MOD;
            ans -= n * (n - 1) * (n - 2) / 2 / 3 - MOD; ans %= MOD;
            ans -= n * (n - 1) * (n - 2) * (n - 3) / 2 / 3 / 4 - MOD; ans %= MOD;
            ans -= n * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 2 / 3 / 4 / 5 - MOD;
            ans %= MOD;
        }
        printf("Case #%d: %lld\n", Cas, ans);
        
    }
}