MathLabs

第4题

全国婚姻委员会要邀请 nn 对夫妇组成 1717 个讨论组。每组成员必须性别相同;任意两组人数之差为 00 或 11;每组至少一人;每人恰好属于一个组。求所有满足条件且 n≤1996n\le1996 的 。
第 3/5 步:把可行性转化为四个不等式
xq≤n≤x(q+1),yq≤n≤y(q+1)xq\le n\le x(q+1),\qquad yq\le n\le y(q+1)
详细分析

xx 个男组能将 nn 名男子分成大小为 q,q+1q,q+1 的组,当且仅当 xq≤n≤x(q+1)xq\le n\le x(q+1);女组同理给出 yq≤n≤y(q+1)yq\le n\le y(q+1)。这些不等式是任何有效安排的必要条件。 yy