Here are some hints. Consider only the formulas .

There are valuations on n variables. For each valuation, how does the sequence oftruth valueslook like? Can we have ?

Use pigeonhole principle where pigeons are pairs of formulas that can have different truth values for some valuation and holes are valuations.