MathDB

4

Part of 1990 Irish Math Olympiad

Problems(2)

2^k Inequality

Source: 1990 IrMO Paper 1 Problem 4

9/30/2017
The real number xx satisfies all the inequalities 2k<xk+xk+1<2k+12^k<x^k+x^{k+1}<2^{k+1} for k=1,2,…,nk=1,2,\dots ,n. What is the greatest possible value of nn?
inequalities
Comparing n-tuples

Source: 1990 IrMO Paper 2 Problem 4

9/30/2017
Let n=2k−1n=2k-1, where k≥6k\ge 6 is an integer. Let TT be the set of all nn-tuples <spanclass=′latex−bold′>x</span>=(x1,x2,…,xn), where, for i=1,2,…,n, xi is 0 or 1.<span class='latex-bold'>x</span>=(x_1,x_2,\dots ,x_n), \text{ where, for } i=1,2,\dots ,n, \text{ } x_i \text{ is } 0 \text{ or } 1. For <spanclass=′latex−bold′>x</span>=(x1,x2,…,xn)<span class='latex-bold'>x</span>=(x_1,x_2,\dots ,x_n) and <spanclass=′latex−bold′>y</span>=(y1,y2,…,yn)<span class='latex-bold'>y</span>=(y_1,y_2,\dots ,y_n) in TT, let d(<spanclass=′latex−bold′>x</span>,<spanclass=′latex−bold′>y</span>)d(<span class='latex-bold'>x</span>,<span class='latex-bold'>y</span>) denote the number of integers jj with 1≤j≤n1\le j\le n such that xj≠xyx_j\neq x_y. ((In particular, d(<spanclass=′latex−bold′>x</span>,<spanclass=′latex−bold′>x</span>)=0)d(<span class='latex-bold'>x</span>,<span class='latex-bold'>x</span>)=0).
Suppose that there exists a subset SS of TT with 2k2^k elements which has the following property: given any element <spanclass=′latex−bold′>x</span><span class='latex-bold'>x</span> in TT, there is a unique <spanclass=′latex−bold′>y</span><span class='latex-bold'>y</span> in SS with d(<spanclass=′latex−bold′>x</span>,<spanclass=′latex−bold′>y</span>)≤3d(<span class='latex-bold'>x</span>,<span class='latex-bold'>y</span>)\le 3.
Prove that n=23n=23.
combinatorics