Maths Olympiad Prep

Library / /272 of 348

Combinatorics Difficulty 5.1 AIME, harder Find the answer

How many functions f:{0,1}3{0,1}f:\{0,1\}^{3} \rightarrow\{0,1\} satisfy the property that, for all ordered triples \left(a_{1}, a_{2}, a_{3}\right) and \left(b_{1}, b_{2}, b_{3}\right) such that aibia_{i} \geq b_{i} for all i,f(a1,a2,a3)f(b1,b2,b3)i, f\left(a_{1}, a_{2}, a_{3}\right) \geq f\left(b_{1}, b_{2}, b_{3}\right)?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider the unit cube with vertices {0,1}3\{0,1\}^{3}. Let O=(0,0,0),A=(1,0,0),B=(0,1,0),C=(0,0,1)O=(0,0,0), A=(1,0,0), B=(0,1,0), C=(0,0,1), D=(0,1,1),E=(1,0,1),F=(1,1,0)D=(0,1,1), E=(1,0,1), F=(1,1,0), and P=(1,1,1)P=(1,1,1). We want to find a function ff on these vertices such that f(1,y,z)f(0,y,z)f(1, y, z) \geq f(0, y, z) (and symmetric representations). For instance, if f(A)=1f(A)=1, then f(E)=f(F)=f(P)=1f(E)=f(F)=f(P)=1 as well, and if f(D)=1f(D)=1, then f(P)=1f(P)=1 as well. We group the vertices into four levels: L0={O},L1={A,B,C},L2={D,E,F}L_{0}=\{O\}, L_{1}=\{A, B, C\}, L_{2}=\{D, E, F\}, and L3={P}L_{3}=\{P\}. We do casework on the lowest level of a 1 in a function. - If the 1 is in L0L_{0}, then ff maps everything to 1, for a total of 1 way. - If the 1 is in L1L_{1}, then f(O)=0f(O)=0. If there are 31 's in L1L_{1}, then everything but OO must be mapped to 1, for 1 way. If there are 21 's in L1L_{1}, then f(L2)=f(L3)=1f\left(L_{2}\right)=f\left(L_{3}\right)=1, and there are 3 ways to choose the 21 's in L1L_{1}, for a total of 3 ways. If there is one 1, then WLOG f(A)=1f(A)=1. Then f(E)=f(F)=f(P)=1f(E)=f(F)=f(P)=1, and f(D)f(D) equals either 0 or 1. There are 32=63 \cdot 2=6 ways to do this. In total, there are 1+3+6=101+3+6=10 ways for the lowest 1 to be in L1L_{1}. - If the lowest 1 is in L2L_{2}, then f(O)=f(L1)=0f(O)=f\left(L_{1}\right)=0. If there are 31 's in L2L_{2}, there is one way to make ff. If there are 21 's, then we can pick the 21 's in 3 ways. Finally, if there is one 1, then we pick this 1 in 3 ways. There are 1+3+3=71+3+3=7 ways. - The lowest 1 is in L3L_{3}. There is 1 way. - There are no 1's. Then ff sends everything to 0. There is 1 way. In total, there are 1+10+7+1+1=201+10+7+1+1=20 total ff^{\prime} 's.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.