Hints for the Problems
This chapter contains hints for all the problems present at the end of the theory chapters. The purpose of these hints is to help the reader if he is stuck. It is intended that reading one sentence of the hint should help the reader, and if further help i
- PDF / 270,159 Bytes
- 12 Pages / 477 x 684 pts Page_size
- 16 Downloads / 215 Views
Hints for the Problems
8.1
Hints for Chap. 1
Hint 1.1 Count the number of ways to choose the rows and columns in which you are going to place the towers. Hint 1.2 Notice that the number of women that have a man to their left is the same as the number of men who have a woman to their right. How can you count that set? Hint 1.3 Consider a set of n elements. First choose k of them and paint them red. Then choose r red elements and paint them blue. Then choose s blue elements and paint them green. How does the set end up painted? Hint 1.4 First choose in which order it is going to put on the shoes and in which order it is going to put on the socks. Then choose the way in which the spider is going to choose a foot to put something on it (either a sock or shoe). Why is this the same as the number of ways to order twice the numbers from 1 to 8 in a list? Hint 1.5 Paint the first column in any way. How many ways are there to paint the rest of the board? Hint 1.6 Count the number of lists according to how many of their elements are different from zero. Hint 1.7 Show that for all i,
|Ai ∩Ai+1 | |Ai |·|Ai+1 |
≤ 12 .
Hint 1.8 Show that for any non-empty even set of columns S there is a row that differs from the top one exactly in S. P. Soberón, Problem-Solving Methods in Combinatorics, DOI 10.1007/978-3-0348-0597-1_8, © Springer Basel 2013
101
102
8
Hints for the Problems
Hint 1.9 Consider the problem with cards from 1 to n and apply induction on n. Try some small cases to determine how many distributions you want to prove there are. Hint 1.10 Show that
n2 k=0 k k
n
=
n2 k=0 (n − k) k .
n
Hint 1.11 Show that if you already have t1 , t2 , . . . , tk with k ≤ 99, then you can choose tk+1 . Hint 1.12 Show that
ms s
r
=
mm−r r
m−s
.
Hint 1.13 Let 2x be the sum of all written numbers. Let A be the subset of written numbers with the biggest possible sum that does not exceed x. Show that if it is not possible to label the numbers as the problem asks then, for each r, all the written numbers k with 1 ≤ k ≤ r are in A. Hint 1.14 Consider the section formed by m consecutive sides and the diagonal that joins the two extremes. Show by strong induction that if m ≤ 100, then in a triangulation of this section we can find at most m2 isosceles triangles with two good segments as sides and that if m > 1003, then we can find at most m2 of these triangles.
8.2
Hints for Chap. 2
Hint 2.1 Show that given any 5 integers, there are 3 of them such that their sum is divisible by 3. Hint 2.2 How many persons are there to shake their hands with? Hint 2.3 Show that there are at most n2 representatives. Construct the seating order by induction. Hint 2.4 Show that if a + b > n then there is such pair. If a + b ≤ n, construct a situation where no such pair exists. Hint 2.5 Use the pigeonhole principle on the pairs (Fk , Fk+1 ) modulo 10n . Hint 2.6 Write the numbers as 2i · j with j odd. Hint 2.7 Number the vertices from 1 to 2007 and consider the sets of 4 of consecutive vertices. How large must k be so t
Data Loading...
