题目链接：《推销员》【NOIP 2015】

令第i$i$家住户为Vi$V_i$。令当X=i$X=i$时，使总疲劳度最大的情况下推销的i$i$个住户集合为Ui$U_i$，最大疲劳度为Wi.$W_i.$

证明命题：∀i∈[1,N−1],Ui⊆Ui+1.$\mathrm{\forall }i\in [1,N-1],U_i\subseteq U_{i+1}.$

---

Ⅰ.$Ⅰ.$当i=1$i=1$时：

假设U1⊈U2$U_1⊈U_2$，不妨设{V1}=U1,{V2,V3}=U2,S2<S3.$\{V_1\}=U_1,\{V_2,V_3\}=U_2,S_2<S_3.$

1∘,S1>S2$1^{\circ },S_1>S_2$（如图1)

有

由于W1$W_1$为当X=1$X=1$时最大疲劳度，因此有2S1+A1>2S3+A3$2S_1+A_1>2S_3+A_3$，则

对应的实际情景是，在X=2$X=2$时，选择V2,V3$V_2,V_3$推销的疲劳度没有选择V1,V2$V_1,V_2$的疲劳度大，则选择V2,V3$V_2,V_3$推销不能使疲劳度最大，即

又由V3$V_3$选取的任意性可得，∀i(S2<Si,i≠1),都有Vi∉U2$\mathrm{\forall }i(S_2<S_i,i\ne 1),都有V_i\notin U_2$，因此${\rm{Ⅰ}}中假设不成立，且有

2∘,S1<S2<S3$2^{\circ },S_1<S_2<S_3$（如图2）

假设A1>A2$A_1>A_2$，则有

此时选择V1,V3$V_1,V_3$的疲劳度大于选择V2,V3$V_2,V_3$的疲劳度，因此V1∈U2,V2∉U2$V_1\in U_2,V_2\notin U_2$，与Ⅰ中假设矛盾，因此$Ⅰ中假设矛盾，因此$ 2^\circ $中假设不成立，即

又由于S1<S2$S_1<S_2$，因此有

因此V1∉U1,V2∈U1$V_1\notin U_1,V_2\in U_1$，有

与Ⅰ$Ⅰ$中假设自相矛盾。

综上，当i=1$i=1$时，Ui⊆Ui+1$U_i\subseteq U_{i+1}$，即U1⊆U2$U_1\subseteq U_2$。

---

Ⅱ.$Ⅱ.$假设当i<k(k∈[2,N])$i<k(k\in [2,N])$时命题成立，则当i=k$i=k$时：

假设Ui⊈Ui+1$U_i⊈U_{i+1}$，不妨设{V1,V2,V3,…,Vk}=Ui,{V∘1,V∘2,V∘3,…,V∘k+1}=Ui+1,Sk<Sk−1<⋯<S2<S1,S∘k+1<S∘k<⋯<S∘2<S∘1.$\{V_1,V_2,V_3,\dots ,V_k\}=U_i,\{V_1^{\circ },V_2^{\circ },V_3^{\circ },\dots ,V_{k+1}^{\circ }\}=U_{i+1},S_k<S_{k-1}<\cdots <S_2<S_1,S_{k+1}^{\circ }<S_k^{\circ }<\cdots <S_2^{\circ }<S_1^{\circ }.$

1∘,S∘1>S1$1^{\circ },S_1^{\circ }>S_1$（如图3）

根据上述证明可得：A1,A2,…,Ak$A_1,A_2,\dots ,A_k$一定是在V1$V_1$左侧的最大的k个，即

若∃Vx,S1<Sx<S∘1,Ax>A1$\mathrm{\exists }{V}_x,S_1<S_x<S_1^{\circ },A_x>A_1$，则Vx∈Uk,V1∉Uk$V_x\in U_k,V_1\notin U_k$，矛盾。（其对应的实际情景为，当X=k$X=k$时，选择V1$V_1$推销不如选择Vx$V_x$推销。）

因此，A1,A2,…,Ak$A_1,A_2,\dots ,A_k$一定都在Uk+1$U_{k+1}$中，即Uk⊆Uk+1$U_k\subseteq U_{k+1}$

2∘,S∘1<Sk$2^{\circ },S_1^{\circ }<S_k$（如图4）

由于当i<k(k∈[2,N])$i<k(k\in [2,N])$时命题成立，则

有

因此，V∘1∉Uk+1,Vi∈Uk+1$V_1^{\circ }\notin U_{k+1},V_i\in U_{k+1}$，该种情况不成立。

3∘,Sp+1<S∘1<Sp(p∈[1,k−1])$3^{\circ },S_{p+1}<S_1^{\circ }<S_p(p\in [1,k-1])$（如图5）

由上述证明可得，Vp+1,Vp+2,…,Vk$V_{p+1},V_{p+2},\dots ,V_k$是V∘1$V_1^{\circ }$左边最大的若干个，因此一定有Vp+1,Vp+2,…,Vk∈Uk+1$V_{p+1},V_{p+2},\dots ,V_k\in U_{k+1}$

只考虑Vp,Vp+1,…,V1$V_p,V_{p+1},\dots ,V_1$，该种情况等价于当X=p$X=p$时的情况Ⅱ.,2∘$Ⅱ.,2^{\circ }$，不成立。

---

根据Ⅰ、Ⅱ$Ⅰ、Ⅱ$以及第二数学归纳法可知，原命题成立，即∀i∈[1,N−1],Ui⊆Ui+1.$\mathrm{\forall }i\in [1,N-1],U_i\subseteq U_{i+1}.$