<p>Sixteen chairs are arranged in a row. Eight people each select a chair in which to sit so that no person sits next to two other people. Let <img alt="$N$" height="12" src="https://latex.artofproblemsolving.com/f/c/9/fc97ef67268cd4e91bacdf12b8901d7036c9a056.png" width="16" /> be the number of subsets of <img alt="$16$" height="13" src="https://latex.artofproblemsolving.com/9/a/5/9a5b4928c8fe50ce3c2428da3bee3505e891b788.png" width="17" /> chairs that could be selected. Find the remainder when <img alt="$N$" height="12" src="https://latex.artofproblemsolving.com/f/c/9/fc97ef67268cd4e91bacdf12b8901d7036c9a056.png" width="16" /> is divided by <img alt="$1000$" height="13" src="https://latex.artofproblemsolving.com/6/e/e/6ee927e1332358c96c62c277441c907c4f51057f.png" width="35" />.</p>

Question No: 335

Sixteen chairs are arranged in a row. Eight people each select a chair in which to sit so that no person sits next to two other people. Let $N$ be the number of subsets of $16$ chairs that could be selected. Find the remainder when $N$ is divided by $1000$ .

Editorial

Tags: Combinatorics

Question Details