Difference between revisions of "User:Quantum-phantom"

Revision as of 07:34, 14 March 2024

This message is regarding [url=https://artofproblemsolving.com/community/c594864h3265596p30137934]this post[/url]. [quote="fura3334"][b]Problem 10[/b] (unclear source) For a positive integer $n$ , denote by $f(n)$ the number of ways to represent $n$ as the sum of powers of 2. Different orders [color=#960000]are[/color] considered different representations, e.g. $4+1+1$ and $1+4+1$ are two different representations of $6$ . Call $n$ "good" if $f(n)$ is even. Let $A$ be the largest number of consecutive good numbers in $\{1,2,\cdots,2025\}$ . Find the remainder when $A$ is divided by 1000.[/quote]

I just read [color=#960000]are[/color] as [color=#960000]aren't[/color]. (yesterday)

Let $n=a_1+a_2+\cdots$ where all $a_i$ are powers of $2$. If $a_1=1$, then $a_2+a_3+\dots=n-1$, with $f(n-1)$ choices; If $a_1=2$, then $a_2+a_3+\dots=n-2$, with $f(n-2)$ choices... So $f(n)=\sum\limits_{i=0}^{\left\lfloor\log_2n\right\rfloor}f\left(n-2^i\right)$.

We use induction on $n$ to show that $f(n)$ is odd iff $n$ is in the form of $2^t-1$, where $t$ is a natural number.

@@ Line 1: / Line 1: @@
-<asy>
+This message is regarding [url=https://artofproblemsolving.com/community/c594864h3265596p30137934]this post[/url].
-usepackage("tkz-euclide");
+[quote="fura3334"][b]Problem 10[/b]
-label("\begin{tikzpicture}[scale=2.5]
+(unclear source)
-\tkzDefPoint(0:1){C}\tkzDefPoint(180:1){B}\tkzDefPoint(0:0){O}
+For a positive integer <math>n</math>, denote by <math>f(n)</math> the number of ways to represent <math>n</math> as the sum of powers of 2. Different orders [color=#960000]are[/color] considered different representations, e.g. <math>4+1+1</math> and <math>1+4+1</math> are two different representations of <math>6</math>. Call <math>n</math> "good" if <math>f(n)</math> is even. Let <math>A</math> be the largest number of consecutive good numbers in <math>\{1,2,\cdots,2025\}</math>. Find the remainder when <math>A</math> is divided by 1000.[/quote]
-\tkzDefPoint(47:1){E}\tkzDefPoint(123:1){F}
-\tkzInterLL(B,F)(C,E)\tkzGetPoint{A}
+I just read [color=#960000]are[/color] as [color=#960000]aren't[/color]. (yesterday)
-\tkzDefPoint(270:1){M}\tkzInterLL(B,C)(M,E)\tkzGetPoint{X}
-\tkzInterLL(B,C)(M,F)\tkzGetPoint{Y}
+Let \(n=a_1+a_2+\cdots\) where all \(a_i\) are powers of \(2\). If \(a_1=1\), then \(a_2+a_3+\dots=n-1\), with \(f(n-1)\) choices; If \(a_1=2\), then \(a_2+a_3+\dots=n-2\), with \(f(n-2)\) choices... So \(f(n)=\sum\limits_{i=0}^{\left\lfloor\log_2n\right\rfloor}f\left(n-2^i\right)\).
-\tkzInterLL(B,E)(C,F)\tkzGetPoint{H}
-\tkzInterLL(A,H)(C,B)\tkzGetPoint{D}
+We use induction on \(n\) to show that <math>f(n)</math> is odd iff <math>n</math> is in the form of \(2^t-1\), where \(t\) is a natural number.
-\tkzInterLC(H,A)(O,B)\tkzGetPoints{z}{Z}
-\tkzDrawArc(O,C)(B)\tkzDrawPoints(A,...,F,H,X,Y,Z)
-\tkzDrawSegments(A,B B,C C,A A,D B,E E,X F,Y C,F)
-\tkzDrawSegments[dashed](Z,Y X,Z Z,B Z,C)
-\tkzDefLine[tangent at=Z](O)\tkzGetPoint{tan}
-\tkzDrawLine[add=.4 and -.6](Z,tan)
-\tkzDefTriangleCenter[circum](X,Y,Z)
-\tkzGetPoint{T}\tkzDrawCircle(T,X)
-\tkzLabelPoints[below](X,Y)\tkzLabelPoints[above right](Z,D,E)
-\tkzLabelPoints[below left](H,B)\tkzLabelPoints[below right](C)
-\tkzLabelPoints[above left](A,F)
-\end{tikzpicture}",origin);
-</asy>

Page

Toolbox

Search

Difference between revisions of "User:Quantum-phantom"

Revision as of 07:34, 14 March 2024