1. X is a set with n elements. Find the number of triples (A, B, C), where A, B, C are subsets of X, such that A is a subset of B and B is a subset of C. 

2. Let m and n be integers greater than 1. Consider an m*n rectangular grid of points in the plane. Some k of these points are colored red in such a way that no three red points are the vertices of a right-angled triangle, two of whose sides are parallel to the sides of the grid. Determine the greatest possible value of k for any given values of m,n > 1.

Source: unknown

1. X is a set with n elements. Find the number of triples (A, B, C), where A, B, C are subsets of X, such that A is a subset of B and B is a subset of C.

Answer: 4ⁿ.  Each element of X is in one of these four sets: A, B\A, C\B, or X\C, and the 4ⁿ possible assignments of elements to sets uniquely generates a triple (A, B, C)

2. Let m and n be integers greater than 1. Consider an m*n rectangular grid of points in the plane. Some k of these points are colored red in such a way that no three red points are the vertices of a right-angled triangle, two of whose sides are parallel to the sides of the grid. Determine the greatest possible value of k for any given values of m,n > 1.

k ≤ m+n-2.

Suppose we have k ≥ m+n-1 red points, and no red triangle. We can interchange rows or interchange columns without affecting whether or not there's a red triangle, so let's move all the rows with two or more red points to the top, and all the columns with two or more red points to the left.  Now the m*n rectangle is divided into four smaller rectangles.  The upper-left rectangle must have at least one row and at least one column, by the pigeonhole principle, since k > m and k > n.  But none of the points in the upper-left sub-rectangle are red, because if they were, they would be part of a red triangle.  Now let's find an upper limit of the number of red points outside the upper-left rectangle.  There are at most n-1 columns that contain 1 or 0 red points each, and at most m-1 rows that contain 1 or 0 red points each, so there are at most m+n-2 red points altogether, a contradiction.

To show a coloring exists in which k=m+n-2, follow this procedure: color red every point of the first row, except the upper left point. Color red every point of the first column, except the upper left point.  Now the number of red points is m+n-2, and there is no red triangle.