$\textbf{Multiplication}$

In the multiplication problem below, $A$, $B$, $C$, and $D$ are different digits. What is $A+B$? $$\begin{array}{cccc}& A & B & A\\ \times & & C & D\\ \hline C & D & C & D\\ \end{array}$$

$\textbf{Lying Politicians}$

Suppose $125$ politicians sit around a conference table. Each politician either always tells the truth or always lies. (Statements of a liar are never completely true, but can be partially true.) Each politician now claims that the two people beside him or her are both liars. What are the maximum possible number and minimum possible number of liars?

$\textbf{Lily Pads}$

There are $24$ lily pads shown below. A toad can jump from one pad to an adjacent one either horizontally or vertically, but not diagonally. Can this toad visit all the pads without stopping at a pad for more than once? It can choose any pad to start its journey.

There are $100$ tigers, $100$ foxes, and $100$ monkeys in the animal kingdom. Tigers always tell the truth; Foxes always tell lies; and monkeys sometimes tell the truth but sometimes not. These $300$ animals are divided into $100$ groups, each of which has exactly two of the same kind and one of another kind. Now comes the Kong Fu Panda. He asks every animal: "is there a tiger in your group?" and receives $138$ "yes" answers. Then he asks everyone: "is there a fox in your group?" and receives $188$ positive answer this time. Find the number of monkeys who tell the truth both time.

There are $2015$ people standing in a circle, counting $1$ and $2$ in turn continuously. Those who count $2$ will be out. For example, people who stand at initial positions of $2, 4, \dots, 2014, 1, 3, \dots$ etc will be out. The game goes on until there is only one person remaining in the circle. What is his initial position?

$\textbf{Cutting Pizza}$

Assume you have a magical pizza in the shape of an infinite plane. You have a magical pizza cutter that can cut an infinite line, but it can only be used $14$ times. To share with as many of your friends as possible, you cut the pizza in a way that maximizes the number of pieces (the pizza is too heavy to be lifted up). How many finite pieces of pizza do you have?

To build roads between $16$ cities so that one can travel from any city to any other city by passing through at most one other city. What is the minimum number of roads that the city with the most road has?

As shown in the figure, in a regular triangular house, all the rooms are in the shape of regular triangles. There are doors between adjacent rooms. Starting from one of the rooms, go through the doors to visit other rooms, without repeating rooms or leaving the house. Including the starting room, how many rooms can be visited?

There are $7$ pieces of paper on a table. Cut some of them into $7$ each and put them back to the table. Repeat this process as many times as you wish. Is it possible to have $1990$ pieces of paper on the table at some moment?

$\textbf{Cover the Board}$

Joe cuts off the top left corner and the bottom right corner of an $8\times 8$ board, and then tries to cover the remaining board using thirty-one $1\times 2$ smaller pieces. Is it possible? Note: a smaller piece can be rotated, but cannot be further broken up.

$\textbf{Cover the Board (II)}$

Joe cuts off a $2\times 2$ corner from an $8\times 8$ board, and then tries to cover the remaining part using $15$ L-shaped grids made of $4$ grids as shown. Is it possible?

$\textbf{Cards Game (Sum Fifteen)}$

There are nine cards laid out on a table, numbered $1$ through $9$. Two players, Joe and John, take turns to pick up one card a time (and once a card is picked up, it is out of play). As soon as one of these two players has the sum of three of cards equal $15$ , that player wins. Who will win if both players adopt the best strategy?

$\textbf{Heaps of Beans}$

A game starts with four heaps of beans, containing $3$, $4$, $5$ and $6$ beans, respectively. The two players move alternately. A move consists of taking either one bean from a heap, provided at least two beans are left behind in that heap, or a complete heap of two or three beans. The player who takes the last bean wins. Does the first or second player have a winning strategy?

$\textbf{Passing the Bridge}$

It is a dark and stormy night. Four people must evacuate from an island to the mainland. The only link is a narrow bridge which allows passage of two people at a time. Moreover, the bridge must be illuminated, and the four people have only one lantern among them. After each passage to the mainland, if there are still people on the island, someone must bring the lantern back. When they cross the bridge individually, the four people take $2$, $4$, $8$ and $16$ minutes, respectively. Crossing the bridge in pairs, the slower speed is used. What is the minimum time for the entire evacuation?

Five friends sat in a movie theater in a row containing $5$ seats, numbered $1$ to $5$ from left to right. (The directions "left" and "right" are from the point of view of the people as they sit in the seats.) During the movie Ada went to the lobby to get some popcorn. When she returned, she found that Bea had moved two seats to the right, Ceci had moved one seat to the left, and Dee and Edie had switched seats, leaving an end seat for Ada. In which seat had Ada been sitting before she got up?

Initially, a chip is placed in the upper-left corner square of a $n\times m$ grid of squares as shown. The chip can move in an $L$-shaped pattern, moving two squares in one direction (up, right, down or left) and then moving one square in a corresponding perpendicular direction. What is the minimum number of $L$-shaped moves needed to move the chip from its initial location to the square marked “$X$”?

$\textbf{Prisoners' Problem}$

One hundred prisoners will be lined up. Each one will be assigned either a red hat or a blue hat. No one can see the color of his or her own hat. However, each person is able to see the color of the hat worn by every person in front of him or her. That is, for example, the last person in line can see the colors of the hats on $99$ people in front of him or her; and the first person, who is at the front of the line, cannot see the color of any hat. Beginning with the last person in line, and then moving to the $99^{th}$ person, the $98^{th}$, etc., each will be asked to name the color of his or her own hat. He or she can only answer "red" or "blue". If the color is correctly named, the person lives; if not, the person is shot dead on the spot. Everyone in line is able to hear all the responses but not the gunshots. Before being lined up, the $100$ prisoners are allowed to discuss a strategy aiming to save as many of them as possible. How many people can be saved if they can agree on a good strategy?

As a more challenging question, what if the hats can have $100$ known different colors instead of $2$?

$\textbf{Flip the Grid}$

Given two grids shown below, is it possible to transform ($a$) to ($b$) after a series of operations? In each operation, one can change all the signs in either one entire row or one entire column.

There are $100$ lights lined up in a long room. Each light has its own switch and is currently off. The room has an entry door and an exit door. There are $100$ people lined up outside the entry door. Each light is numbered consecutively from $1$ to $100$. So is each person.

Person No. $1$ enters the room, switches on every light, and exits. Person No. $2$ enters and flips the switch on every second light (i.e. turn off lights $2$, $4$, $6$...). Person No. $3$ enters and flips the switch on every third light (i.e. toggle lights $3$, $6$, $9$...). This continues until all $100$ people have passed through the room. How many of the lights are on at the end?

$\textbf{Eel}$

An eel is a polyomino formed by a path of unit squares that makes two turns in opposite directions. (Note that this means the smallest eel has four cells.) For example, the polyomino shown below is an eel. What is the maximum area of a $1000\times 1000$ grid of unit squares that can be covered by eels without overlap?

$\textbf{Key Set}$

A sensitive location is protected by a door with multiple locks. This place has $11$ workers. The regulation requires that any combination of six workers can open all the locks, but any combination of five cannot. What is the minimal number of locks and how to distribute the keys?

$\textbf{Two Doormen}$

Two doormen are guarding two rooms. One room contains tons of gold and the other is empty. Among these two doormen, one is honest who always tells the truth and the other is a liar who always gives false answers. While they know each other well, you do not know who is honest and who is not. If you are given just one chance to ask one question to one of them, what can you do in order to find out which room contains the gold?

$\textbf{Toggler's Problem}$

Among a group of $100$ people, only one is a truth teller and the rest $99$ are togglers. A truth teller always tells the truth. A toggler will tell the truth and a lie in an alternating fashion. That is, after he or she tells the truth the first time, this person will tell a lie next time. However, if his or her first answer is false, then the next answer will be true. It is unknown whether a toggler's first answer is the truth or a lie.

If all these people know who is the truth teller, how many questions do you need to ask in order to identify the truth teller?

$\textbf{Connect the Lights}$

You are in a control room which has three switches. Each switch controls one of three lights in another room. Once you leave the control room, you can not touch the switches again. How can you figure out which switch controls which light?

$\textbf{What Bear}$

Joe leaves his campsite and hikes south for $3$ miles. He then turns east and hikes for $3$ miles. Finally he turns north and hikes for $3$ miles. At this moment he sees a bear inside his tent eating his food! What color is the bear?