One of the students in my class, Undergraduate Seminar on Discrete Mathematics, asks if the exchange property of a matroid can be strengthened to the following, of which I was completely unaware.

Strong basis exchange property. For every pair of bases B_1, B_2 and x_1 \in B_1, there exists x_2 \in B_2 such that both B_1 - x_1 + x_2 and B_2 + x_1 - x_2 are still bases.

As it turns out, Brualdi proved back in 1969 the strong exchange property (Theorem 2) in Comments on bases in dependence structures.

I record below the proof which showcases the benefit of viewing matroids both graphically and linear-algebraically.

As per Aaron Berger‘s suggestion, we use a graphic matroid to motivate the proof. Suppose T_1 and T_2 are two spanning trees of a connected graph G and e_1 is an edge in T_1. Clearly, when the edge e_1 is also in T_2, we can simply exchange e_1 with itself. Assume from now that e_1 is not in T_2. Note that T_2 + e_1 contains a unique cycle C, each edge of which can be “traded” to T_1. To be more precise, for every e_2 \in C, T_2 + e_1 - e_2 is still a spanning tree. It is then easy to see that adding back some edge from C - e_1 can reconnect the two connected components resulted from removing e_1 from T_1.

As the unique cycle (or circuit) C plays a central role in the above argument, one can show the same concept is valid in any matroid.

Lemma (Fundamental circuit). For every independent set I, if an element e satisfies that I + e is dependent, then I + e contains a unique circuit C, called the fundamental circuit. Moreover, for every f \in C, I + e - f is independent.

Proof of strong basis exchange property. Without loss of generality, we may assume that e_1 \not\in B_2. As B_2 is a maximal independent set and B_2 + e_1 is dependent, there is a unique circuit C \subseteq B_2 + e_1 such that B_2 + e_1 - e_2 is independent for every e_2 \in C.

Finally we resort to our intuition of representable matroids. Since e_1 \in \mathrm{span}(C - e_1) \subseteq \mathrm{span}(B_1 + C - e_1), we have \mathrm{span}(B_1 + C - e_1) = \mathrm{span}(B_1 + C), hence B_1 + C - e_1 contains a basis, say B_1'. By the ordinary exchange property for B_1 - e_1 and B_1', there is e_2 \in B_1' - (B_1 - e_1) \subseteq C - e_1 such that B_1 - e_1 + e_2 is independent. ∎

Here is a problem from Week of Code 29 hosted by Hackerrank.

Problem. Given two integers q_1 and q_2 (1\le q_1 \le q_2 \le 10^{15}), find and print a common fraction p/q such that q_1 \le q \le q_2 and \left|p/q-\pi\right| is minimal. If there are several fractions having minimal distance to \pi, choose the one with the smallest denominator.

Note that checking all possible denominators does not work as iterating for 10^{15} times would exceed the time limit (2 seconds for C or 10 seconds for Ruby).

The problem setter suggested the following algorithm in the editorial of the problem:

Given q, it is easy to compute p such that r(q) := p/q is the closest rational to \pi among all rationals with denominator q.

Start from q = q_1, and at each step increase q by the smallest denominator d of a semiconvergent such that r(q+d) is closer to \pi than r(q). Repeat until q exceeds q_2.

Given q, let d = d(q) be the smallest increment to the denominator q such that r(q+d) is closer to \pi than r(q). To justify the algorithm, one needs to prove the d is the denominator of one of the semiconvergents. The problem setter admits that he does not have a formal proof.

Inspired by the problem setter’s approach, here is a complete solution to the problem. Note that \pi should not be special in this problem, and can be replaced by any other irrational number \theta. Without loss of generality, we may assume that \theta\in(0,1).

We first introduce the Farey intervals of \theta.

Start with the interval (0/1, 1/1).

Suppose the last interval is (a/b, c/d). Cut it by the mediant of a/b and c/d and choose one of the intervals (a/b, (a+c)/(b+d)), ((a+c)/(b+d), c/d) that contains \theta as the next interval.

We call the intervals appeared in the above process Farey intervals of \theta. For example, take \theta = \pi - 3 = 0.1415926.... The Farey intervals are:

The Farey sequence of order n, denoted by F_n, is the sequence of completely reduced fractions between 0 and 1 which when in lowest terms have denominators less than or equal to n, arranged in order of increasing size. Fractions which are neighboring terms in any Farey sequence are known as a Farey pair. For example, Farey sequence of order 5 is F_5 = (0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1).

Lemma 1. For every Farey interval (a/b, c/d) of \theta, the pair (a/b, c/d) is a Farey pair. Conversely, for every Farey pair (a/b, c/d), if \theta \in (a/b, c/d), then (a/b, c/d) is a Farey interval.
We say p/q is a good rational approximation of \theta if every rational betweenp/q and \theta (exclusive) has a denominator greater than q.

By the definition of Farey sequence, incorporating with Lemma 1, we know that

Lemma 2. A rational is an endpoint of a Farey interval of \theta if and only if it is a good rational approximation of \theta.

In fact, one can show that the endpoints of Farey intervals and semiconvergents of continued fraction are the same thing! Thereof, the problem setter’s claim follows immediately from:

Proposition. Given q, let r(q) = p / q be the rational closest to \theta with denominator q. If d = d(q) is the minimal increment to q such that r(q + d) = (p + c) / (q + d) is closer to \theta than r(q), then c/d is a good rational approximation.

Remark. The proposition states that the increments to p/q always come from a good rational approximation. It is stronger than the problem setter’s statement, which only asserts that the increment to the q comes from a good rational approximation.

Proof. In (x, y)-plane, plot the trapezoid defined by

\left| y/x - \theta \right| < \left|p/q - \theta\right|, q < x < q + d.

Also we interpret rational numbers p/q, (p+c)/(q+d) as points A = (q, p), B = (q+d, p+c). Let the line through (q, p) parallel to y=\theta x intersect the vertical line x = q+d at C = (q+d, p+\theta d). By the definition of d, we know that the trapezoid does not contain lattice points. In particular, there is no lattice point in the interior of the triangle ABC. In the coordinate system with origin at A, B has coordinate (d, c) and the line through A, C is y = \theta x. Since triangle ABC contains no lattice points, there is no (b, a) with b < d such that a/b is between \theta and c/d. In other words, c/d is a good rational approximation. ∎

Here is a fine print of the algorithm. Because floats may not have enough precision for the purpose of computation, we will instead use a convergent of the continuous fraction of \pi instead. All the computations will then happen in \mathbb{Q}. Finally, we present the algorithm.

P = Rational(5706674932067741, 1816491048114374) - 3
# find endpoints of Farey intervals
a, b, c, d = 0, 1, 1, 1
farey = [[a,b],[c,d]]
while (f = b + d) <= max - min
farey << [e = a + c, f]
if P < Rational(e, f)
c, d = e, f
else
a, b = e, f
end
end
min, max = gets.split.map(&:to_i)
p_min = (P * q).round
# increase p_min/min by frations in farey
while min <= max
c, d = nil, nil
farey.each do |a, b|
break if min + b > max
if (Rational(p_min + a, min + b) - P).abs < (Rational(p_min, min) - P).abs
c, d = a, b
break
end
end
break if d == nil
p_min += c; min += d
end
puts "#{p_min + 3 * min}/#{min}"

I had never expected that Feb 19, 2017 would be the last day we say farewell to each.

We used to talk about math puzzles, from blue-eyed islander puzzle to the hardest logic puzzle ever, every time on the bus from or to Shuk. We joked about the possibility that the apple cores we throw in the Carmel national park would one day become apple trees. We had plans to host a hot-pot party and introduce Mahjong to our Israeli friends…

I realized that all these can only expressed in past tense when I saw you forever asleep in Eilat.

Here is a list of things I have experienced during the first week in Israel and some tips for those of you who plan to visit me in Haifa!

Hainan airline has a direct flight from Beijing to Tel Aviv, and they have a resting area for transiting passengers in Beijing.

If this is your first time in Israel, make sure your arrival day is not Saturday or any holiday. Saturday (or holiday) means almost no public transportation, almost no restaurants and fewer people on the street whom you can ask help from.

Most Israelis are quite friendly and speak decent English. Even if someone does not speak English at all, he or she is always able to grab someone closeby to help.

You can exchange all major currencies (eg. US dollars, Chinese yuan) for new Israeli shekels at the airport in Tel Aviv at Bank Hapoalim. Expectedly, the rate is not as good as what you can get outside the airport. A lot of places accept major credit cards, such as Visa and Mastercard. Some places ask for a purchase of 20 shekels or more if you use credit card.

The vending machines for train tickets did not accept my Mastercard. The ticket from the airport to Haifa (Hof Hacarmel station) costs 35 shekels. The train is on platform 2 and it has WiFi connection. Use Google map to tell which station you are arriving if you, like myself, do not understand enough Hebrew.

The train from Tel Aviv to Haifa goes along the coastal line of the mediterranean sea. Highway no.2 lies between the rails and the coast, which resembles highway no.1 in California.

Bus no.11 goes from Hof Hacarmel to Technion. The bus fare is something slightly less than 6 shekels. Moovit is a must for public transportation planning, and it can send you notification when you are approaching at your destination.

Uber and Lyft do not have services in Haifa (but Uber does in Tel Aviv). People use Gett (aka Get Taxi) to call cabs. Since tipping is not required for taxi, remember to turn off automatic tipping in the app. You can use my code GTMLIYK for 15 shekels off your 1st ride.

The most popular messaging app is WhatsApp. I was asked for my WhatsApp contact for quite a few times.

Google Fi (global cellular service including data) works quite well in Israel. For the first week, I’ve heavily relied on my smart phone for navigation, transportation and information retrieving. It’s probably a good idea to carry a power bank. The outlet sockets in Israel are Type C and H.

Other random observations:

On Sunday, the train is full of soldiers. A few were probably carrying M4 carbines when I was on the train.

The rent for the property listed online (eg. yod2.co.il or Facebook group) usually does not include city tax and building management fee.

Some apartments in Haifa have a separate room for the toilet only.

You give all the checks for the rent to the landlord when you sign the contract. Technion is able to write a guarantee letter to the landlord saying that they will freeze your last payment as the security deposit.

You will not be able to change the PIN, set by the bank, of your debit card, at least for Bank Leumi, the other major bank in Israel besides Bank Hapoalim.

Hebrew calendar and Chinese calendar are both lunisolar, so they are similar in a lot of ways. Friday and Saturday are weekends in Israel.

High schoolers can choose how difficult the math they want to learn. For example, calculus (including formulas like e^{i\theta} = \cos \theta + i\sin\theta) is offered in high schools.

However, most high school graduates need to go to army for 2-3 years and it’s hard to recall what they have learnt after the army. Top students might have the option to delay their military service.

Pork and shellfish are not Kosher, so you will not be able to see them in most supermarkets. It is also not Kosher to eat meat with milk.

\binom{M}{k} – the family of all subsets of M of size k;

\binom{M}{<\omega} – the family of all finite subsets of M;

\binom{M}{\omega} – the family of all infinite subsets of M;

The infinite Ramsey theorem, in its simplest form, states that for every partition \binom{\mathbb{N}}{k} = \mathcal{F}_1 \sqcup \dots \sqcup \mathcal{F}_r, there exists an infinite set M\subset \mathbb{N} such that \binom{M}{k}\subset \mathcal{F}_i for some i\in [r]. The Nash-Williams‘ partition theorem can be seen as a strengthening of the infinite Ramsey theorem, which considers a partition of a subset of \binom{\mathbb{N}}{<\omega}.

Notations.

\mathcal{F}\restriction M – \mathcal{F}\cap 2^M, that is, the set \{s\in\mathcal{F} : s\subset M\}.

s \sqsubset t , where s,t are subsets of \mathbb{N} – s is an initial segment of t, that is s = \{n\in t : n \le \max s\}.

Definition. Let set \mathcal{F} \subset \binom{\mathbb{N}}{<\omega}.

\mathcal{F} is Ramsey if for every partition \mathcal{F}=\mathcal{F}_1\sqcup \dots\sqcup\mathcal{F}_r and every M\in\binom{\mathbb{N}}{\omega}, there is N\in\binom{M}{\omega} such that \mathcal{F}_i\restriction N = \emptyset for all but at most one i\in[r].

\mathcal{F} is a Nash-Williams family if for all s, t\in\mathcal{F}, s\sqsubset t \implies s = t.

Theorem (Nash-Williams 1965). Every Nash-Williams family is Ramsey.

The proof presented here is based on the proof given by Prof. James Cummings in his Infinite Ramsey Theory class. The purpose of this rewrite is to have a proof that resembles the one of the infinite Ramsey theorem.

Notation. Let s\in\binom{\mathbb{N}}{<\omega} and M\in\binom{\mathbb{N}}{\omega}. Denote $$[s, M] = \left\{t \in \binom{\mathbb{N}}{<\omega} : t \sqsubset s \text{ or } (s \sqsubset t \text{ and } t\setminus s \subset M)\right\}.$$

Definition. Fix \mathcal{F}\subset \binom{\mathbb{N}}{<\omega} and s\in \binom{\mathbb{N}}{<\omega}.

Macceptss if [s, M]\cap \mathcal{F}\neq \emptyset and Mrejectss otherwise;

Mstrongly acceptss if every infinite subset of M accepts s;

Mdecidess if M either rejects s or strongly accepts it.

We list some properties that encapsulates the combinatorial characteristics of the definitions above.

Properties.

If M decides (or strongly accepts, or rejects) s and N\subset M, then N decides (respectively strongly accepts, rejects) s as well.

For every M\in\binom{\mathbb{N}}{\omega} and s\in\binom{\mathbb{N}}{<\omega}, there is N_1\in\binom{M}{\omega} deciding s. Consequently, there is N_2\in\binom{M}{\omega} deciding every subset of s.

Proof of Theorem. Enough to show that if \mathcal{F} = \mathcal{F}_1\sqcup \mathcal{F}_2, then for every M\in\binom{\mathbb{N}}{\omega}, there is infinite N\in \binom{M}{\omega} such that F_i \restriction N = \emptyset for some i\in[2].

We are going to use \mathcal{F}_1 instead of \mathcal{F} in the definitions of “accept”, “reject”, “strongly accept” and “decide”. Find N\in \binom{M}{\omega} that decides \emptyset. If N rejects \emptyset, by definition \mathcal{F}_1\restriction N = [\emptyset, N]\cap \mathcal{F}_1 = \emptyset. Otherwise N strongly accepts \emptyset.

Inductively, we build a decreasing sequence of infinite sets N \supset N_1 \supset N_2\supset \dots , an increasing sequence of natural numbers n_1, n_2, \dots, and maintain that n_i\in N_i, n_i < \min N_{i+1} and that N_i strongly accepts every s\subset \{n_j : j < i\}. Initially, we take N_1 = N as N strongly accepts \emptyset.

Suppose N_1 \supset \dots \supset N_i and n_1 < \dots < n_{i-1} have been constructed. In the following lemma, when taking M = N_i and s = \{n_j : j < i\}, it spits out m and N, which are exactly what we need for n_i and N_{i+1} to finish the inductive step.

Lemma. Suppose M\in\binom{\mathbb{N}}{\omega}, s\in\binom{\mathbb{N}}{<\omega} and \max s < \min M. If M strongly accepts every subset of s, then there are m \in M and N \in \binom{M}{\omega} such that n < \min N and N strongly accepts every subset of s\cup \{n\}

Proof of lemma. We can build M = M_0 \supset M_1\supset M_2 \supset \dots such that for every i, m_i := \min M_i < \min M_{i+1} and M_{i+1} decides every subset of s\cup \{m_i\}. It might happen that M_{i+1} rejects a subset of s\cup \{m_i\}. However, we claim that this cannot happen for infinitely many times.

Otherwise, by the pigeonhole principle, there is t\subset s such that I = \{i : M_{i+1} \text{ rejects }t\cup\{m_{i}\}\} is infinite. Let M' = \{m_i : i\in I\}. Note that [t, M'] \subset \cup_i [t\cup\{m_i\}, M_{i+1}], and so [t,M']\cap \mathcal{F}_1\subset \cup_i \left([t\cup\{m_i\}, M_{i+1}]\cap\mathcal{F}_1\right) = \emptyset. Hence M'\subset M rejects t\subset s, which is a contradiction.

Now we pick one i such that M_{i+1} strongly accepts every subset of s\cup\{m_i\}, and it is easy to check that m = m_i and N = M_{i+1} suffice. ∎

Finally, we take N_\infty = \{n_1, n_2, \dots\}. For any s\in\binom{N_\infty}{<\omega}, there is i such that s\subset \{n_1, \dots, n_{i-1}\}. Note that N_i strongly accepts s and N_\infty\subset N_i. Therefore N_\infty (strongly) accepts s, that is [s, N_\infty]\cap \mathcal{F}_1 \neq \emptyset, and say t\in [s, N_\infty]\cap \mathcal{F}_1. Because t\in\mathcal{F}_1 and \mathcal{F} = \mathcal{F}_1 \sqcup \mathcal{F}_2 is a Nash-Williams family, s\notin \mathcal{F}_2. ∎

Although using blackboard and chalk is the best option for a math talk for various reasons, sometimes due to limit on the time, one has to make slides to save time on writing. The most common tools to create slides nowadays are LaTeX and Beamer.

When I was preparing for my talk at Vancouver for Connections in Discrete Mathematics in honor of the work of Ron Graham, as it is my first ever conference talk, I decided to ditch Beamer due to my lack of experience. Finally, I ended up using html+css+javascript to leverage my knowledge in web design.

The javascript framework I used is reveal.js. Though there are other options such as impress.js, reveal.js fits better for a math talk. One can easily create a text-based presentation with static images / charts. The framework also has incorporated with MathJax as an optional dependency, which can be added with a few lines of code. What I really like about reveal.js as well as impress.js is that they provide a smooth spatial transition between slides. However, one has to use other javascript library to draw and animate diagrams. For that, I chose raphael.js, a javascript library that uses SVG and VML for creating graphics so that users can easily, for example, create their own specific chart. The source code of the examples on the official website is really a good place to start.

To integrate reveal.js and raphael.js to achieve a step-by-step animation of a diagram, I hacked it by adding a dummy fragment element in my html document so that reveal.js can listen to the fragmentshown event and hence trigger raphael.js to animate the diagram. In cases where the diagrams are made of html elements, I used jQuery to control the animation. Here is my favorite animation in the slides generated by jQuery.

However, one has to make more effort to reverse the animation made by raphael.js or jQuery if one wants to go backwards in slides. I did not implement any reverse animation since I did not plan to go back in slides at all.

In case there is no internet access during the presentation, one has to have copies of all external javascript libraries (sometimes also fonts), which, in my case, are MathJax, raphael.js and jQuery. In order to use MathJax offline, one need to configure reveal.js.

Currently, my slides only work on Chrome correctly. There is another bug that I have not figured out yet. If I start afresh from the first slide, then my second diagram generated by Raphael is not rendered correctly. I got around it by refreshing the slide where the second diagram lives. This is still something annoying that I would like to resolve.

After all, I really like this alternative approach of making slides for math presentation because it enables me to implement whatever I imagine.

Hausdorff moment problem asks for necessary and sufficient conditions that a given sequence (m_n) with m_0=1 be the sequence of moments of a random variable X supported on [0,1], i.e., \operatorname{E}X^n=m_n for all n.

In 1921, Hausdorff showed that (m_n) is such a moment sequence if and only if the sequence is completely monotonic, i.e., its difference sequences satisfy the equation (D^r m)_s \ge 0 for all r, s \ge 0. Here D is the difference operator on the space of real sequences (a_n) given by D a = (a_{n} - a_{n+1}).

The proof under the fold follows the outline given in (E18.5 – E18.6) Probability with Martingales by David Williams.

Proof of Necessity. Suppose (m_n) is the moment sequence of a random variable X supported on [0,1]. By induction, one can show that (D^r m)_s = \operatorname{E}(1-X)^rX^s. Clearly, as X is supported on [0,1], the moment sequence is completely monotonic.

Proof of Sufficiency. Suppose (m_n) is a completely monotonic sequence with m_0 = 1.

Define F_n(x) := \sum_{i \le nx}{n\choose i}(D^{n-i}m)_i. Clearly, F_n is right-continuous and non-decreasing, and F_n(0^-) = 0. To prove F_n(1) = 1, one has to prove the identity \sum_{i}{n\choose i}(D^{n-i}m)_i = m_0.

A classical trick. Since the identity above is about vectors in the linear space (over the reals) spanned by (m_n) and the linear space spanned by (m_n) is isomorphic to the one spanned by (\theta^n), the identity is equivalent to \sum_{i}{n\choose i}(D^{n-i}\theta)_i = \theta^0, where \theta_n = \theta^n. Now, we take advantage of the ring structure of \mathbb{R}[\theta]. Notice that (D^{r}\theta)_s = (1-\theta)^r\theta^s. Using the binomial theorem, we obtain \sum_{i}{n\choose i}(D^{n-i}\theta)_i = \sum_{i}{n\choose i}(1-\theta)^{n-i}\theta^i = (1-\theta + \theta)^n = \theta^0.

Therefore F_n is a bona fide distribution function. Define m_{n, k} := \int_{[0,1]} x^kdF_n(x), i.e., m_{n,k} is the kth moment of F_n. We now find an explicit formula for m_{n,k}.

Noticing that F_n is constant, say c_{n,i}, on [\frac{i}{n}, \frac{i+1}{n}), for all i=0, \dots, n-1 and c_{n,i} is a linear combination of m_0, \dots, m_n, we know that m_{n,k} = \sum_{i=0}^n a_{n,k,i}m_i.

Just like what we did in proving the identity, we use the special case m_n = \theta^n to compute the coefficients a_i = a_{n,k,i}, where 0 \le \theta \le 1. In this case, F_n(x) = \sum_{i \le nx}{n\choose i}(D^{n-i}\theta)_i = \sum_{i\le nx}{n\choose i}(1-\theta)^{n-i}\theta^i, m_{n,k} = \sum_{i=0}^n a_{i}\theta^i.

Now consider the situation in which a coin with probability \theta is tossed at times 1,2,\dots. The random variable H_k is 1 if the kth toss produces heads, 0 otherwise. Define A_n := (H_1 + \dots + H_n)/n. It is immediate from the formula of F_n that F_n is the distribution function of A_n, and so m_{n,k} is the kth moment of A_n. However, one can calculate the kth moment of A_n explicitly. Let f\colon [k] \to [n] be chosen uniformly at random, Im_f be the cardinality of the image of f and denote by p_i = p_{n,k,i} := \operatorname{Pr}(Im_f = i). Using f, Im_f and p_i, we obtain \begin{aligned}\operatorname{E}A_n^k & = \operatorname{E}\left(\frac{H_1 + \dots + H_n}{n}\right)^k = \operatorname{E}H_{f(1)}\dots H_{f(k)} \\ & = \operatorname{E}\operatorname{E}[H_{f(1)}\dots H_{f(k)}\mid Im_f] = \operatorname{E}\theta^{Im_f} = \sum_{i=0}^n p_{i}\theta^i.\end{aligned} Therefore, for all \theta\in [0,1], we know that \sum_{i=0}^n a_i\theta^i = \sum_{i=0}^n p_i\theta^i, and so a_i = p_i for all i=0,\dots, n.

As both (a_i) and (p_i) do not depend on m_i, a_i = p_i holds in general. Since p_k = p_{n, k, k} = \prod_{i=0}^{k-1}(1-i/n)\to 1 as n\to\infty and p_i = 0 for all i > k, we know that \lim_n m_{n,k}= m_k.

Using the Helly–Bray Theorem, since (F_n) is tight, there exists a distribution function F and a subsequence (F_{k_n}) such that F_{k_n} converges weakly to F. The definition of weak convergence implies that \int_{[0,1]} x^k dF(x) = \lim_n \int_{[0,1]}x^k dF_{k_n}(x) = \lim_n m_{k_n,k} = m_k. Therefore, the random variable X with distribution function F is supported on [0,1] and its kth moment is m_k. ∎

欺诈猜数游戏在甲和乙之间进行，甲和乙都知道正整数 k 和 n。游戏开始时，甲先选定两个整数 x 和 N，其中 1\leq x\leq N。甲告诉乙 N 的值，但对 x 守口如瓶。乙试图通过提问来获得与 x 相关的信息：每次提问，乙任选一个由若干正整数组成的集合S（可以重复使用之前提问中使用过的集合），问甲“x是否属于S？”。乙可以提任意数量的问题。每次提问之后，甲立刻回答是或否，甲可以说谎话，但在任意连续 k+1 次回答中至少有一次回答是真话。

在乙问完所有想问的问题之后，乙必须指出一个至多包含 n 个正整数的集合 X，若 x 属于 X，则乙获胜；否则甲获胜。证明：对所有充分大的整数 k，存在整数 n\geq 1.99^k，使得乙无法保证获胜。

为了解决第二个问题，需要从甲的角度考虑问题，每一次回答问题后，使得乙无法缩小 x 范围。

为此我们考虑贪心策略：甲每次在乙提出的集合和其补集中选择元素较多的那个集合。很明显这个策略有一个弱点：如果乙每次提问都问“x 是不是 1 呢？”那甲如果每次只顾眼前利益，应当回答“不是。”但经过 k+1 轮之后，甲就能轻松排除 1，从而缩小 x 的范围。

于是甲的策略必须是一种折中的策略，既要顾及眼前的利益，又不能放弃长期的利益。我们设定 N=n+1。

于是甲在觉得到底要选择乙提出的集合或是其补集前，对 1 到 n+1 中每个数都进行打分。甲对 i 的打分是 a^{m_i}，其中a = 1.999 而 m_i 满足 i 在最近连续 m_i 次选择的集合中都不出现。根据每个元素的打分，甲在 S 和 S^c 中选择会使得之后整个集合总分较低的那个集合。

We shall show an upper bound on the Stirling number of the second kind, a byproduct of a homework exercise of Probabilistic Combinatorics offered by Prof. Tom Bohman.

Definition. A Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by S(n,k).

Proposition. For all n, k, we have S(n,k) \leq \frac{k^n}{k!}\left(1-(1-1/m)^k\right)^m.

Proof. Consider a random bipartite graph with partite sets U:=[n], V:=[k]. For each vertex u\in U, it (independently) connects to exactly one of the vertices in V uniformly at random. Suppose X is the set of non-isolated vertices in V. It is easy to see that \operatorname{Pr}\left(X=V\right) = \frac{\text{number of surjections from }U\text{ to }V}{k^n} = \frac{k!S(n,k)}{k^n}.

On the other hand, we claim that for any \emptyset \neq A \subset [k] and i \in [k]\setminus A, \operatorname{Pr}\left(i\in X \mid A\subset X\right) \leq \operatorname{Pr}\left(i\in X\right). Note that the claim is equivalent to \operatorname{Pr}\left(A\subset X \mid i\notin X\right) \geq \operatorname{Pr}\left(A\subset X\right). Consider the same random bipartite graph with V replaced by V':=[k]\setminus \{i\} and let X' be the set of non-isolated vertices in V'. The claim is justified since \operatorname{Pr}\left(A\subset X\mid i\notin X\right) = \operatorname{Pr}\left(A\subset X'\right) \geq \operatorname{Pr}\left(A\subset X\right).

Set A:=[i-1] in above for i = 2, \ldots, k. Using the multiplication rule with telescoping the conditional probability, we obtain \begin{aligned}\operatorname{Pr}\left(X=V\right) =& \operatorname{Pr}\left(1\in X\right)\operatorname{Pr}\left(2\in X \mid [1]\subset X\right) \\ & \ldots \operatorname{Pr}\left(k\in X\mid [k-1]\subset X\right)\\ \leq & \operatorname{Pr}\left(1\in X\right)\operatorname{Pr}\left(2\in X\right)\ldots\operatorname{Pr}\left(k\in X\right) \\ = & \left(1-(1-1/m)^k\right)^m.\end{aligned}∎