# Difference between revisions of "2018 AIME I Problems/Problem 12"

(Adding solution) |
Math101010 (talk | contribs) |
||

Line 1: | Line 1: | ||

+ | ==Problem== | ||

+ | For every subset <math>T</math> of <math>U = \{ 1,2,3,\ldots,18 \}</math>, let <math>s(T)</math> be the sum of the elements of <math>T</math>, with <math>s(\emptyset)</math> defined to be <math>0</math>. If <math>T</math> is chosen at random among all subsets of <math>U</math>, the probability that <math>s(T)</math> is divisible by <math>3</math> is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m</math>. | ||

+ | |||

+ | ==Solution 1== | ||

Rewrite the set after mod3 | Rewrite the set after mod3 | ||

1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 | 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 | ||

Line 58: | Line 62: | ||

− | Solution 2 | + | ==Solution 2== |

+ | Consider the numbers {1,4,7,10,13,16}. Each of those are congruent to 1mod3. There is <math>{6 \choose 0}=1</math> way to choose zero numbers <math>{6 \choose 1}=6</math> ways to choose 1 and so on. There ends up being <math>{6 \choose 0}+{6 \choose 3}+{6 \choose 6}</math> possible subsets congruent to 0mod 3. There are <math>2^6=64</math> possible subsets of these numbers. | ||

+ | |||

+ | ==Solution 3== | ||

+ | Notice that six numbers are <math>0\pmod3</math>, six are <math>1\pmod3</math>, and six are <math>2\pmod3</math>. Having numbers <math>0\pmod3</math> will not change the remainder when <math>s(T)</math> is divided by <math>3</math>, so we can choose any number of these in our subset. We ignore these for now. The number of numbers that are <math>1\pmod3</math>, minus the number of numbers that are <math>2\pmod3</math>, must be a multiple of <math>3</math>, possibly zero or negative. We can now split into cases based on how many numbers that are <math>1\pmod3</math> are in the set. | ||

+ | |||

+ | Case 1- <math>0</math>, <math>3</math>, or <math>6</math> integers: There can be <math>0</math>, <math>3</math>, or <math>6</math> integers that are <math>2\pmod3</math>. We can choose these in <math>\left(\binom60+\binom63+\binom66\right)\cdot\left(\binom60+\binom63+\binom66\right)=(1+20+1)^2=484</math> ways. | ||

+ | |||

+ | Case 2- <math>1</math> or <math>4</math> integers: There can be <math>2</math> or <math>5</math> integers that are <math>2\pmod3</math>. We can choose these in <math>\left(\binom61+\binom64\right)\cdot\left(\binom62+\binom65\right)=(6+15)^2=441</math> ways. | ||

+ | |||

+ | Case 3- <math>2</math> or <math>5</math> integers: There can be <math>1</math> or <math>4</math> integers that are <math>2\pmod3</math>. We can choose these in <math>\left(\binom62+\binom65\right)\cdot\left(\binom61+\binom64\right)=(15+6)^2=441</math> ways. | ||

+ | |||

+ | Adding these up, we get that there are <math>1366</math> ways to choose the numbers such that their sum is a multiple of three. Putting back in the possibility that there can be multiples of <math>3</math> in our set, we have that there are <math>1366\cdot\left(\binom60+\binom61+\binom62+\binom63+\binom64+\binom65+\binom66+\right)=1366\cdot2^6</math> subsets <math>T</math> with a sum that is a multiple of <math>3</math>. Since there are <math>2^{18}</math> total subsets, the probability is <math>\frac{1366\cdot2^6}{2^{18}}=\frac{683}{2^{11}}</math>, so the answer is <math>\boxed{683}</math>. |

## Revision as of 22:51, 8 March 2018

## Contents

## Problem

For every subset of , let be the sum of the elements of , with defined to be . If is chosen at random among all subsets of , the probability that is divisible by is , where and are relatively prime positive integers. Find .

## Solution 1

Rewrite the set after mod3 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 All 0s can be omitted Case 1 No 1 No 2 1 Case 2 222 20 Case 3 222222 1 Case 4 12 6*6=36 Case 5 12222 6*15=90 Case 6 1122 15*15=225 Case 7 1122222 15*6=90 Case 8 111 20 Case 9 111222 20*20=400 Case 10 111222222 20 Case 11 11112 15*6=90 Case 12 11112222 15*15=225 Case 13 1111122 6*15=90 Case 14 1111122222 6*6=36 Case 15 111111 1 Case 16 111111222 20 Case 17 111111222222 1 Total 1+20+1+36+90+225+90+20+400+20+90+225+90+36+1+20+1=484+360+450+72=1366 P=1362/2^12=683/2^11 ANS=683

## Solution 2

Consider the numbers {1,4,7,10,13,16}. Each of those are congruent to 1mod3. There is way to choose zero numbers ways to choose 1 and so on. There ends up being possible subsets congruent to 0mod 3. There are possible subsets of these numbers.

## Solution 3

Notice that six numbers are , six are , and six are . Having numbers will not change the remainder when is divided by , so we can choose any number of these in our subset. We ignore these for now. The number of numbers that are , minus the number of numbers that are , must be a multiple of , possibly zero or negative. We can now split into cases based on how many numbers that are are in the set.

Case 1- , , or integers: There can be , , or integers that are . We can choose these in ways.

Case 2- or integers: There can be or integers that are . We can choose these in ways.

Case 3- or integers: There can be or integers that are . We can choose these in ways.

Adding these up, we get that there are ways to choose the numbers such that their sum is a multiple of three. Putting back in the possibility that there can be multiples of in our set, we have that there are subsets with a sum that is a multiple of . Since there are total subsets, the probability is , so the answer is .