2022 AIME I Problems/Problem 12
Revision as of 00:01, 18 February 2022 by Stevenyiweichen (talk | contribs)
Problem
For any finite set , let
denote the number of elements in
. Define
where the sum is taken over all ordered pairs
such that
and
are subsets of
with
.
For example,
because the sum is taken over the pairs of subsets
giving
.
Let
, where
and
are relatively prime positive integers. Find the remainder when
is divided by
1000.
Solution
For each element , denote
, where
(resp.
).
Denote .
Denote .
Hence,
Therefore,
This is in the lowest term.
Therefore, modulo 1000,
~Steven Chen (www.professorchenedu.com)