Combinatorics & Algebra
3. If \(S\) is a finite set of non-zero vectors in the plane, then a maximal subset is a subset whose vector sum has the largest possible magnitude. Show that if \(S\) has \(n\) vectors, then there are at most \(2n\) maximal subsets of \(S\). Give a set of 4 vectors with 8 maximal subsets and a set of 5 vectors with 10 maximal subsets. S
5. Let \(ABCD\) be a regular tetrahedron. Let \(M\) be a point in the plane \(ABC\) and \(N\) a point different from \(M\) in the plane \(ADC\). Show that the segments \(MN\), \(BN\) and \(MD\) can be used to form a triangle. S
6. Let \(a,b,c\) be positive integers such that \(a\) and \(b\) are relatively prime and \(c\) is relatively prime to \(a\) or \(b\). Show that there are infinitely many solutions to \(m^a+n^b=k^c\), where \(m,n,k\) are distinct positive integers. S
7. \(ABCDEF\) is a convex hexagon with \(AB=BC\), \(CD=DE\), \(EF=FA\). Show that \[ \frac{BC}{BE}+\frac{DE}{DA}+\frac{FA}{FC}\ge\frac{3}{2}. \] When does equality occur? S
9. \(ABC\) is a non-isosceles triangle with incenter \(I\). The smaller circle through \(I\) tangent to \(CA\) and \(CB\) meets the smaller circle through \(I\) tangent to \(BC\) and \(BA\) at \(A'\) (and \(I\)). \(B'\) and \(C'\) are defined similarly. Show that the circumcenters of \(\triangle AIA'\), \(\triangle BIB'\), \(\triangle CIC'\) are collinear. S
10. Find all positive integers \(n\) such that if \(p(x)\) is a polynomial with integer coefficients such that \(0\le p(k)\le n\) for \(k=0,1,2,\dots,n+1\) then \(p(0)=p(1)=\dots=p(n+1)\). S
11. \(p(x)\) is a polynomial with real coefficients such that \(p(x)>0\) for \(x\ge0\). Show that \((1+x)^n p(x)\) has non-negative coefficients for some positive integer \(n\). S
12. Let \(p\) be prime. \(q(x)\) is a polynomial with integer coefficients such that \(q(k)=0\) or \(1\mod p\) for every positive integer \(k\), and \(q(0)=0,q(1)=1\). Show that the degree of \(q(x)\) is at least \(p-1\). S
13. In town \(A\) there are \(n\) girls and \(n\) boys and every girl knows every boy. Let \(a(n,r)\) be the number of ways in which \(r\) girls can dance with \(r\) boys, so that each girl knows her partner. In town \(B\) there are \(n\) girls and \(2n-1\) boys such that girl \(i\) knows boys \(1,2,\dots,2i-1\) (and no others). Let \(b(n,r)\) be the number of ways in which \(r\) girls from town \(B\) can dance with \(r\) boys from town \(B\) so that each girl knows her partner. Show that \(a(n,r)=b(n,r)\). S
14. Let \(b>1\) and \(m>n\). Show that if \(b^m-1\) and \(b^n-1\) have the same prime divisors then \(b+1\) is a power of 2. S
15. If an infinite arithmetic progression of positive integers contains a square and a cube, show that it must contain a sixth power. S
16. \(ABC\) is an acute triangle with incenter \(I\) and circumcenter \(O\). Let \(AD,BE\) be altitudes, and \(AP,BQ\) angle bisectors. Show that \(D,I,E\) are collinear iff \(P,O,Q\) are collinear. S
18. In acute triangle \(ABC\), let the altitudes be \(AD,BE,CF\). The line through \(D\) parallel to \(EF\) meets \(AC\) at \(Q\) and \(AB\) at \(R\). The line \(EF\) meets \(BC\) at \(P\). Show that the midpoint of \(BC\) lies on the circumcircle of \(PQR\). S
19. Let \(x_1\ge x_2\ge x_3\ge\cdots\ge x_{n+1}=0\). Show \[ \sqrt{x_1+x_2+\cdots+x_n}\le(\sqrt{x_1}-\sqrt{x_2})+\sqrt{2}(\sqrt{x_2}-\sqrt{x_3})+\cdots+\sqrt{n}(\sqrt{x_n}-\sqrt{x_{n+1}}). \] S
20. \(ABC\) is a triangle. \(D\) is a point on \(BC\). The line \(AD\) meets the circumcircle again at \(X\). Let \(P,Q\) be feet from \(X\) to \(AB,AC\). Show that \(PQ\) is tangent to the circle on diameter \(XD\) iff \(AB=AC\). S
22. Do there exist real-valued functions \(f,g\) with \(f(g(x))=x^2\) and \(g(f(x))=x^3\)? Do there exist such that \(f(g(x))=x^2\) and \(g(f(x))=x^4\)? S
23. Let \(ABCD\) be a convex quadrilateral with diagonals meeting at \(X\). If \(XA\sin A+XC\sin C=XB\sin B+XD\sin D\), show that \(ABCD\) is cyclic. S
25. In triangle \(ABC\), bisectors meet the circumcircle again at \(K,L,M\). Let \(X\) on \(AB\). Lines through \(X\) parallel to \(AK,BL\) intersect perpendiculars from \(B,A\). Show that \(KP,LQ,MX\) concur. S
26. Find the minimum of \(x_0+x_1+\cdots+x_n\) for non-negative reals \(x_i\) with \(x_0=1\) and \(x_i\le x_{i+1}+x_{i+2}\). S
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου