## Problem of the Day #347: Evaluating Boolean ExpressionsFebruary 29, 2012

Posted by Alex in : potd , add a comment

Saketh wants to evaluate the Boolean algebra expression $(AB + CD)(AC + BD)$. The values of $A$, $B$, $C$, and $D$ are randomly generated. In order to evaluate the expression, Saketh will uncover variables, revealing their values, one at a time in whatever order he desires. Given that Saketh chooses optimally, what is the expected number of variables whose values must be revealed before Saketh can evaluate the expression?

Note: $AB$ denotes $A \text{ and } B$ and $C+D$ denotes $C \text{ or } D$.

## Problem of the Day #346: Fun with FunctionsFebruary 28, 2012

Posted by Saketh in : potd , add a comment

Ana is investigating a function $f(n)$ defined for all positive integers $n$. She knows that $f(ab) = f(a)\cdot f(b)$ for all relatively prime positive integers $a$ and $b$, and that $f(p+q) = f(p)+f(q)$ for all primes $p$ and $q$. Given these facts, help her find the value of $f(2012)$.

## Problem of the Day #345: Binary BoundsFebruary 27, 2012

Posted by Saketh in : potd , 1 comment so far

Gillie is counting certain binary strings. He defines $f(n,k)$ to be the number of binary strings of length $n$ that do not contain any substring of $k$ consecutive zeroes or ones.

Let $a(k)$ be the greatest real number such that $f(n,k) \geq a(k)^n$ for every positive integer $n$. Find $a(6)$.

Bonus: How does $a(n)$ behave in the general case? Is it possible to express $a(n)$ as an elementary function of $n$?

## Problem of the Day #344: Triangles from Polygon VerticesFebruary 26, 2012

Posted by Alex in : potd , add a comment

A $24$-sided regular polygon is centered at $(0, 0)$ and at least one of its points lies on the $x$-axis. How many non-degenerate triangles formed from three vertices of the polygon contain the origin?

## Problem of the Day #343: Counting Binary StringsFebruary 25, 2012

Posted by Alex in : potd , 1 comment so far

A binary string is a string where each character is either a ’0′ or a ’1′. How many binary strings are there of length $100,000$ that contain none of $\{001, 100, 1110, 1010\}$ as a substring?

## Problem of the Day #342: The LightbulbFebruary 24, 2012

Posted by Saketh in : potd , add a comment

A room contains a single light controlled by a wall switch. Initially, it is either turned on or off. Then, $10$ people pass through the room one by one, each with a $\frac{1}{5}$ chance of deciding to flip the switch.

Finally, Muthu enters the room and sees that the lightbulb is turned on. Determine the probability that the light was initially on.

## Problem of the Day #341: A Matter of DivisibilityFebruary 23, 2012

Posted by Saketh in : potd , add a comment

Kevin Au, a famous number theorist, is counting positive integers less than or equal to $10000$. However, he ignores all numbers divisible by more than one single-digit prime. How many such numbers will he count?

## Problem of the Day #340: (ir)Rationality of $\sqrt{2}$February 22, 2012

Posted by Albert in : potd , add a comment

Thanks to my dad for this problem.

While no positive integers $M$ and $N$ satisfy $M^2 = 2 \cdot N^2$, determine (with proof) whether there are infinitely many pairs of integers $M$ and $N$ such that $M^2 = 2 \cdot N^2 + 1$.
Thus, as $M, N$ increase, $\frac{M}{N}$ becomes a better approximation for $\sqrt{2}$.

## Problem of the Day #339: Arjun Likes FoodFebruary 21, 2012

Posted by Alex in : potd , add a comment

Inspired by a problem from the 2012 Spotify Code Quest

Arjun likes food. He starts at coordinate $0$ with $500$ units of food, and for each distance of $1$ he moves, he consumes $1$ unit of food. Saketh is at coordinate $100$ and he wants food. What is the maximum amount of food that Arjun can deliver to Saketh? Arjun is allowed to place food on the ground wherever he wishes (so that he can pick it up later), but every time he places food on the ground, half of the quantity is consumed by squirrels.

## Problem of the Day #338: Albert’s QuadrilateralsFebruary 20, 2012

Posted by Saketh in : potd , add a comment

Given any quadrilateral $ABCD$, Albert draws in the points $P$, $Q$, $R$, and $S$ – the midpoints of sides $BC$, $CD$, $DA$, and $AB$ respectively. He then determines the value of $$\frac{AP^2 + BQ^2 + CR^2 + DS^2}{AB^2 + BC^2 + CD^2 + DA^2}$$ What is the largest possible ratio Albert could find?