MathLabs

第4题

全国婚姻委员会要邀请 nn 对夫妇组成 1717 个讨论组。每组成员必须性别相同；任意两组人数之差为 00 或 11；每组至少一人；每人恰好属于一个组。求所有满足条件且 n≤1996n\le1996 的 。
第 5/5 步：为列表中的每个值构造分组
上一步下一步
rm=n−xq,rf=n−yq,0≤rm≤x,0≤rf≤yr_m=n-xq,\quad r_f=n-yq,\quad 0\le r_m\le x,\quad0\le r_f\le y
详细分析

对列表中的每个 nn，不等式给出相应的 xx。取 rm=n−xqr_m=n-xq 个男组为 q+1q+1 人，其余 x−rmx-r_m 个为 qq 人；取 rf=n−yqr_f=n-yq 个女组为 q+1q+1 人，其余 y−rfy-r_f 个为 qq 人。上下界保证这些余数落在相应范围内，故所有条件均满足，充分性得证。 yy