最近在看Steven Skiena写的The Algorithm Design Manual，第二章遇到一个习题，想了一个naive的方法，在网上也没有查到解答。想到这个题是不是会有更一般的解法，希望路过的大神如果有insight的话给点指导 
这个题是这样描述的：
We have 1,000 data items to store on 1,000 nodes. Each node can store copies of exactly three different items. Propose a replication scheme to minimize data loss as nodes fail. What is the expected number of data entries that
get lost when three random nodes fail?
初看这个问题，有以下几个初步想法
1. 显然，每个数据的重要性都是一样的，所以每个数据都应该存储3个备份；
2. 对于任意两个node，它们的交集越少越好，比如两个node存储的数据完全一样，那么它们同时fail掉，丢失一个数据的概率就是10^-3 + 10^-3 + 10^-3，如果这两个node 之间只有一个数据相同，那么丢失一个数据的概率就是10^-3。这也不意味着一个node上存数同一个数据，那样这个node崩溃，会丢失这个数据。同时，我们也不可能让任意两个node的交集为空，这是由第一条决定的。
3. 分析以上两条，问题可以转化为，给定一个1000个元素的集合，找到这个集合的1000个子集，满足：每个子集都有3个元素，每两个子集的交集最多只有一个元素。（感觉一个元素是最能接受的情况，两个会使得丢失数据的概率变大）
我的解法是这样的：
假设数据是{ 1, 2, 3, ..., 1000}，首先把这1000个元素分成小段，每段有3个元素，即
——————————————————————————
1, 2, 3
3, 4, 5
5, 6, 7
7, 8, 9
...
993, 994, 995
995, 996, 997
997, 998, 999
999, 1000, 1
———————————————————————————
可以看出，相邻两小段的首尾元素是相同的，走到最后一段再返回到第一段。
这些小段分别作为结果一部分，一共是 500个 三元素子集。到此时，所有的奇数都被存储了2次。偶数被存储了1次。下面再对所有偶数做相似操作
——————————————————————————————
2， 4， 6
6， 8， 10
...
994, 996, 998
998, 1000, 2
____________________________________________________
这些小段也作为结果的一部分，一共是250个三元素子集。到此，所有4*n+2, n= 0, 1, ..., 249形式的数都被存储了3次。下面再收集其他已经存储两次的数
———————————————————————————————
1, 4, 7
5, 8, 11
...,
993, 996, 999
997, 1000, 3
______________________________________________________
也即对一开始的500小段斜着取，每隔一行取一次。这样又得到了250小段。
至此，一共得到了1000个3元素子集，任意两个子集最多有一个元素相交。三个node同时fail的话，只可能损失一个数据，所以期望是1000*10^-3*10^-3*10^-3 = 10^-6.
此题应该有其他的解法，甚至更一般的解法。感觉是个set cover问题，希望在后面看书的过程中可以找到答案。