12. (16 points) Given an integer $n(n \geqslant 3)$, let $f(n)$ be the minimum number of elements in a subset $A$ of the set $\left\{1,2, \cdots, 2^{n}-1\right\}$ that satisfies the following two conditions:
(i) $1 \in A, 2^{n}-1 \in A$;
(ii) Each element in subset $A$ (except 1) is the sum of two (possibly the same) elements in $A$.
(1) Find the value of $f(3)$;
(2) Prove: $f(100) \leqslant 108$.
12. (1) Let set $A \subseteq\left\{1,2, \cdots, 2^{3}-1\right\}$, and $A$ satisfies (i) and (ii). Then $1 \in A, 7 \in A$.

Since $\{1, m, 7\}(m=2,3, \cdots, 6)$ does not satisfy (ii), hence $|A|>3$.
Also, $\{1,2,3,7\},\{1,2,4,7\},\{1,2,5,7\}$,
$\{1,2,6,7\},\{1,3,4,7\},\{1,3,5,7\}$,
$\{1,3,6,7\},\{1,4,5,7\},\{1,4,6,7\}$,
$\{1,5,6,7\}$

do not satisfy (ii), hence $|A|>4$.
However, the set $\{1,2,4,6,7\}$ satisfies (i) and (ii), so $f(3)=5$.
(2) First, prove:
$$
f(n+1) \leqslant f(n)+2(n=3,4, \cdots) \text {. }
$$

In fact, if $A \subseteq\left\{1,2, \cdots, 2^{n}-1\right\}$ satisfies (i) and (ii), and the number of elements in set $A$ is $f(n)$. Let
$$
B=A \cup\left\{2^{n+1}-2,2^{n+1}-1\right\} \text {. }
$$

Since $2^{n+1}-2>2^{n}-1$, we have
$|B|=f(n)+2$.
Also, $2^{n+1}-2=2\left(2^{n}-1\right)$,
$$
2^{n+1}-1=1+\left(2^{n+1}-2\right) \text {, }
$$

then $B \subseteq\left\{1,2, \cdots, 2^{n+1}-1\right\}$, and set $B$ satisfies
(i) and (ii).
Thus, $f(n+1) \leqslant|B|=f(n)+2$.
Next, prove:
$$
f(2 n) \leqslant f(n)+n+1(n=3,4, \cdots) \text {. }
$$

In fact, let $A \subseteq\left\{1,2, \cdots, 2^{n}-1\right\}$ satisfy
(i) and (ii), and the number of elements in set $A$ is $f(n)$. Let
$$
\begin{aligned}
B= & A \cup\left\{2\left(2^{n}-1\right), 2^{2}\left(2^{n}-1\right), \cdots,\right. \\
& \left.2^{n}\left(2^{n}-1\right), 2^{2 n}-1\right\} .
\end{aligned}
$$

Since $2\left(2^{n}-1\right)<2^{2}\left(2^{n}-1\right)<\cdots$
$$
<2^{n}\left(2^{n}-1\right)<2^{2 n}-1 \text {, }
$$

then $B \subseteq\left\{1,2, \cdots, 2^{2 n}-1\right\}$, and
$$
\begin{array}{l}
|B|=f(n)+n+1 . \\
\text { and } 2^{k+1}\left(2^{n}-1\right) \\
=2^{k}\left(2^{n}-1\right)+2^{k}\left(2^{n}-1\right)(k=0,1, \cdots, n-1), \\
2^{2 n}-1=2^{n}\left(2^{n}-1\right)+\left(2^{n}-1\right),
\end{array}
$$

then $B$ satisfies (i) and (ii).
Thus, $f(2 n) \leqslant|B|=f(n)+n+1$.
From equations (1) and (2), we get
$$
f(2 n+1) \leqslant f(n)+n+3 \text {. }
$$

Repeatedly using equations (2) and (3), we get
$$
\begin{array}{l}
f(100) \leqslant f(50)+51 \\
\leqslant f(25)+26+51 \\
\leqslant f(12)+15+77 \\
\leqslant f(6)+7+92 \\
\leqslant f(3)+4+99=108 .
\end{array}
$$
(Xiong Hua, Gu Hongda, Liu Hongkuang, Li Dayuan, Ye Shengyang)