For every subset $T$ of $U = \{ 1,2,3,\ldots,18 \}$, let $s(T)$ be the sum of the elements of $T$, with $s(\emptyset)$ defined to be $0$. If $T$ is chosen at random among all subsets of $U$, the probability that $s(T)$ is divisible by $3$ is $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m$.
The question asks us for the probability that a randomly chosen subset of the set of the first 18 positive integers has the property that the sum of its elements is divisible by 3. Note that the total number of subsets is $2^{18}$ because each element can either be in or not in the subset. To find the probability, we will find the total numbers of ways the problem can occur and divide by $2^{18}$.
To simplify the problem, let’s convert the set to mod 3:
\[U' = \{1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0\}\]
Note that there are six elements congruent to 0 mod 3, 6 congruent to 1 mod 3, and 6 congruent to 2 mod 3. After conversion to mod three, the problem is the same but we’re dealing with much simpler numbers. Let’s apply casework on this converted set based on $S = s(T')$, the sum of the elements of a subset $T'$ of $U'$.
$\textbf{Case 1: }S=0$
In this case, we can restrict the subsets to subsets that only contain 0. There are six 0’s and each one can be in or out of the subset, for a total of $2^{6} = 64$ subsets. In fact, for every case we will have, we can always add a sequence of 0’s and the total sum will not change, so we will have to multiply by 64 for each case. Therefore, let’s just calculate the total number of ways we can have each case and remember to multiply it in after summing up the cases. This is equivalent to finding the number of ways you can choose such subsets without including the 0's. Therefore this case gives us $\boxed{1}$ way.
$\textbf{Case 2: }S= 3$
In this case and each of the subsequent cases, we denote the number of 1’s in the case and the number of two’s in the case as $x, y$ respectively. Then in this case we have two subcases;
$x, y = 3,0:$ This case has $\tbinom{6}{3} \cdot \tbinom{6}{0} = 20$ ways.
$x, y = 1,1:$ This case has $\tbinom{6}{1} \cdot \tbinom{6}{1} = 36$ ways.
In total, this case has $20+36=\boxed{56}$ ways.
$\textbf{Case 3: }S=6$
In this case, there are 4 subcases;
$x, y = 6,0:$ This case has $\tbinom{6}{6} \cdot \tbinom{6}{0} = 1$ way.
$x, y = 4,1:$ This case has $\tbinom{6}{4} \cdot \tbinom{6}{1} = 90$ ways.
$x, y = 2,2:$ This case has $\tbinom{6}{2} \cdot \tbinom{6}{2} = 225$ ways.
$x, y = 0,3:$ This case has $\tbinom{6}{0} \cdot \tbinom{6}{3} = 20$ ways.
In total, this case has $1+90+225+20=\boxed{336}$ ways.
Note that for each case, the # of 1’s goes down by 2 and the # of 2’s goes up by 1. This is because the sum is fixed, so when we change one it must be balanced out by the other. This is similar to the Diophantine equation $x + 2y= S$ and the total number of solutions will be $\tbinom{6}{x} \cdot \tbinom{6}{y}$. From here we continue our casework, and our subcases will be coming out quickly as we have realized this relation.
$\textbf{Case 4: }S=9$
In this case we have 3 subcases:
$x, y = 5,2:$ This case has $\tbinom{6}{5} \cdot \tbinom{6}{1} = 90$ ways.
$x, y = 3,3:$ This case has $\tbinom{6}{3} \cdot \tbinom{6}{3} = 400$ ways.
$x, y = 1,4:$ This case has $\tbinom{6}{1} \cdot \tbinom{6}{4} = 90$ ways.
In total, this case has $90+400+90=\boxed{580}$ ways.
$\textbf{Case 5: } S=12$
In this case we have 4 subcases:
$x, y = 6,3:$ This case has $\tbinom{6}{6} \cdot \tbinom{6}{3} = 20$ ways.
$x, y = 4,4:$ This case has $\tbinom{6}{4} \cdot \tbinom{6}{4} = 225$ ways.
$x, y = 2,5:$ This case has $\tbinom{6}{2} \cdot \tbinom{6}{5} = 90$ ways.
$x, y = 0,6:$ This case has $\tbinom{6}{0} \cdot \tbinom{6}{6} = 1$ way.
Therefore the total number of ways in this case is $20 + 225 + 90 + 1=\boxed{336}$. 
Here we notice something interesting. Not only is the answer the same as Case 3, the subcases deliver the exact same answers, just in reverse order. Why is that?
We discover the pattern that the values of $x, y$ of each subcase of Case 5 can be obtained by subtracting the corresponding values of $x, y$ of each subcase in Case 3 from 6 ( For example, the subcase 0, 6 in Case 5 corresponds to the subcase 6, 0 in Case 3). Then by the combinatorial identity, $\tbinom{6}{k} = \tbinom{6}{6-k}$, which is why each subcase evaluates to the same number. But can we extend this reasoning to all subcases to save time?
Let’s write this proof formally. Let $W_S$ be the number of subsets of the set $\{1,2,1,2,1,2,1,2,1,2,1,2\}$ (where each 1 and 2 is distinguishable) such that the sum of the elements of the subset is $S$ and $S$ is divisible by 3. We define the empty set as having a sum of 0. We claim that $W_S = W_{18-S}$.
$W_S = \sum_{i=1}^{|D|} \tbinom{6}{x_i}\tbinom{6}{y_i}$ if and only if there exists $x_i, y_i$ that satisfy $0\leq x_i \leq 6$, $0\leq y_i \leq 6$, $x_i + 2y_i = S$, and $D$  is the set of the pairs $x_i, y_i$. This is because for each pair $x_i$, $y_i$ there are six elements of the same residue mod(3) to choose $x_i$ and $y_i$ numbers from, and their value sum must be $S$.
Let all $x_n$, $y_n$ satisfy $x_n = 6-x_i$ and $y_n = 6-y_i$.
We can rewrite the equation $x_i+ 2y_i = S \implies -x_i- 2y_i = -S \implies 6-x_i+ 6-2y_i= 12 - S$
$\implies 6-x_i+12-2y_i = 18-S \implies 6-x_i + 2(6-y_i) = 18-S$
\[\implies x_n + 2y_n = 18 - S\]
Therefore, since $0\leq x_i, y_i\leq 6$ and $x_n = 6-x_i$ and $y_n = 6-y_i$, $0\leq x_n, y_n\leq 6$. As shown above, $x_n + 2y_n = 18 - S$ and since $S$ and 18 are divisible by 3, 18 -$S$ is divisible by 3. Therefore, by the fact that $W_S = \sum_{i=1}^{|D|} \tbinom{6}{x_i}\tbinom{6}{y_i}$, we have that;
$W_{18-S} = \sum_{n=1}^{|D|} \tbinom{6}{x_n}\tbinom{6}{y_n} \implies W_{18-S} =  \sum_{i=1}^{|D|} \tbinom{6}{6-x_i}\tbinom{6}{6-y_i} \implies W_{18-S} =  \sum_{i=1}^{|D|} \tbinom{6}{x_i}\tbinom{6}{y_i} = W_S$, proving our claim.
We have found our shortcut, so instead of bashing out the remaining cases, we can use this symmetry. The total number of ways over all the cases is $\sum_{k=0}^{6} W_{3k} = 2 \cdot (1+56+336)+580 = 1366$. The final answer is $\frac{2^{6}\cdot 1366}{2^{18}} = \frac{1366}{2^{12}} = \frac{683}{2^{11}}.$
There are no more 2’s left to factor out of the numerator, so we are done and the answer is $\boxed{\boxed{683}}$.

~KingRavi