Subcontests
(4)Linear algebra in Olympiads......?
Given a connected graph with n edges, where there are no parallel edges. For any two cycles C,C′ in the graph, define its outer cycle to be
C∗C′={x∣x∈(C−C′)∪(C′−C)}.
(1) Let r be the largest postive integer so that we can choose r cycles C1,C2,…,Cr and for all 1≤k≤r and 1≤i, j1,j2,…,jk≤r, we have
Ci=Cj1∗Cj2∗⋯∗Cjk.
(Remark: There should have been an extra condition that either j1=i or k=1)
(2) Let s be the largest positive integer so that we can choose s edges that do not form a cycle.
(Remark: A more precise way of saying this is that any nonempty subset of these s edges does not form a cycle)
Show that r+s=n.Note: A cycle is a set of edges of the form {AiAi+1,1≤i≤n} where n≥3, A1,A2,…,An are distinct vertices, and An+1=A1. FIGO is perpendicular
Let I,G,O be the incenter, centroid and the circumcenter of triangle ABC, respectively. Let X,Y,Z be on the rays BC,CA,AB respectively so that BX=CY=AZ. Let F be the centroid of XYZ. Show that FG is perpendicular to IO. A beautiful combo problem
A calendar is a (finite) rectangular grid. A calendar is valid if it satisfies the following conditions:(i) Each square of the calendar is colored white or red, and there are exactly 10 red squares.(ii) Suppose that there are N columns of squares in the calendar. Then if we fill in the numbers 1,2,… from the top row to the bottom row, and within each row from left to right, there do not exist N consecutive numbers such that the squares they are in are all white.(iii) Suppose that there are M rows of squares in the calendar. Then if we fill in the numbers 1,2,… from the left-most column to the right-most column, and within each column from bottom to top, there do not exist M consecutive numbers such that the squares they are in are all white. In other words, if we rotate the calendar clockwise by 90∘, the resulting calendar still satisfies (ii).How many different kinds of valid calendars are there? (Remark: During the actual exam, the contestants were confused about what counts as different calendars. So although this was not in the actual exam, I would like to specify that two calendars are considered different if they have different side lengths or if the 10 red squares are at different locations.)