matematikk.net

La $A$ være mengden $A = \{1, 2, 3,\dots, 13\}$. Hvor mange delmengder av $A$ bestående av 3 elementer har en sum som er delelig på 3?
(Med sum mener jeg summen av elementene i undermengden.)

Hvis en delmengde med tre elementer har en sum delelig på $3$, må enten alle elementene være kongruente modulo $3$, eller så må de alle være forskjellige modulo $3$. Nå kan vi telle opp alle muligheter:
\[ \binom{5}{3}+\binom{4}{3}+\binom{4}{3}+5\cdot 4\cdot 4 =98\]
slike delmengder totalt. Finnes det en annen løsning som ikke deler opp i tilfeller?


Oppfølger:
La $A$ være mengden $A=\{1,2,3,\dotsc,13\}$. Hvor mange delmengder av $A$ har en sum som er delelig på $3$?

Flott!

stensrud wrote:Finnes det en annen løsning som ikke deler opp i tilfeller?

Ikke som jeg vet om, jeg løste den på samme måte som deg.

stensrud wrote: Oppfølger:
La $A$ være mengden $A=\{1,2,3,\dotsc,13\}$. Hvor mange delmengder av $A$ har en sum som er delelig på $3$?

Modulo 3 vil elementene i mengden være {1,2,0,1,2,0,1,2,0,1,2,0,1}, altså fire av 0, fem av 1 og fire av 2.

Vi må telle opp antall delmengder som har som sum: 0, 3, 6, 9 og 12.

Antall delmengder (inklusive $\emptyset$) med sum 0 er $2^4=16$.

Antall delmengder med sum 3 er $2^4 \cdot\left ({5\choose 1}{4\choose 1}+{5\choose 3}\right )=480$

Antall delmengder med sum 6 er $2^4\cdot \left({5\choose 4}{4\choose 1}+{5\choose 2}{4\choose 2}+{4\choose 3}\right )=2^4(5*4+10*6+4)=16*84=1344$


Antall delmengder med sum 9 er $2^4\cdot \left ({4\choose 2}{5\choose 5}+{4\choose 3}{5\choose 3}+{4\choose 4}{5\choose 1}\right )=2^4(6*1+4*10+1*5)=16*51=816$

Antall delmengder med sum 12 er $2^4\cdot {4\choose 4}{5\choose 4}=16*5=80$.

Totalt 2736. Til slutt må vi vel trekke fra den tomme mengden, så svaret skulle bli 2735.

Fint! Alternativ løsning:

La $f(x)=\prod_{i=1}^{13}(x^i+1)=\sum_{i=1}^{91}a_ix^i$. Da er antall delmengder med sum delelig med tre lik $\sum_{3\mid i}a_i$. La $\zeta=e^{2\pi i/3}$, og merk at
\[1+\zeta^r+\zeta^{2r}=\begin{cases} 3 & \text{hvis }3\mid r,\\ 0 &\text{hvis } 3\nmid r.\end{cases}\]
Dette betyr at
\[ \sum_{3\mid i} a_i=\frac{f(1)+f(\zeta)+f(\zeta^2)}{3}=\frac{2^{13}+(2^4\zeta+2^4)+(2^4\zeta^2+2^4)}{3}=\frac{2^{13}+2^4}{3}=2736,\]
så svaret er $2736$ eller $2735$, avhengig om vi teller med $\emptyset$ eller ikke.

Elegant!

Forresten, gratulerer med Honourable mention i IMO! Regner dog med du ikke er 100% fornøyd med poengsummen ?

Tusen takk for det! Nei, jeg hadde håpet på 14 poeng: Første dag var jeg rett og slett for treig, og rakk nesten ikke å begynne på oppgave 2/3. På dag to lot jeg være å skrive ned en del av beviset på oppgave 4 (mente det var trivielt), og det hjalp heller ikke at jeg gjorde en liten feil på slutten. Ble derfor trukket 3 poeng totalt på den oppgaven, noe jeg ikke var spesielt happy for

Imponerende å få full score på et IMO-problem, og meget godt gjort å løse både problem 1 og 4! Synd du ikke rakk å prøve på de andre problemene! Regner med at problem 2 og 5 var innen rekkevidde, med mer tid..