Is it possible to write the numbers $17$,$18$,$19$,...$32$ in a $4*4$ grid of unit squares with one number in each square such that if the grid is divided into four $2*2$ subgrids of unit squares ,then the product of numbers in each of the subgrids divisible by $16$?
Problem
Source:
Tags: combinatorics unsolved, combinatorics
07.12.2014 15:28
The solution to this problem is as follows : One of the grid has 32 which is 2^5. So that grid is fulfilling the criteria . There can't be any other even no in this grid . As if it is there , then atleast one of the subgrid will only have $3$ $2$'s in its product which is violating the condition. So the rest of three grids should have four $2$'s in its product . Suppose one grid has $24 $, then that grid sholud have one of the numbers of the set $S_1$ i.e $18,22,26,30$( numbers which are divisible by $2$ but not $4$) .So one of them is used . Now we are left with two nos (set $S_2$) re$20,28$ ( divisible by $4$ but not by$8$ )and the rest of the numbers of $S_1$.So now there are two possibilities : 1. Both the numbers of $S_2$ lie in the same subgrid . 2. Both numbers odf $S_2$lie in different subgrids. 1. If both lie in same subgrid then that grid cant have aany more even numbers . So in the last grid we have three nos of $S_1$ which doesnt fulfill the condition . 2. If both lie in different grids, then in each grid there has to be two nos from the remaining set of numbers of $S_1$. But by PHP , this is not possible. So this can't occur.
07.12.2014 17:54
Hopefully simpler: Taking the highest power of 2 of each number, the problem is equivalent to this- you're given eight coins each worth $0$ dollars (eight odd numbers), four coins each worth $1$ dollars (four integers $n$ such that $v_2(n)=1$), two coins each worth two dollars (two integers $n$ with $v_2(n)= 2$), one coin worth three dollars (24), and one coin worth five dollars (32). Is is possible to divide them into four groups $G_1, G_2, G_3, G_4$ such that the value of each of the groups is $\geq 4$? The answer is no- note that the total value of the coins is 16, so the value of each of the groups must be exactly 4. However, the value of the group which contains the five dollar coin has value at least 5.
07.12.2014 18:03
What I have done........ Place 32 in a grid and turn your attention to other grids ........the product of the 12 numbers must be divisible by $(2^4)^3=2^{12}$. But the product of these numbers is divisible by at most $2^{11}$.Contradiction!
08.12.2014 12:18
As'each grid is divisible nbhm 16 hence total square is divisible by16*16*16*16 or highest power of 2 should be 16 but multiplying numbers 17*18*19... we get highest power of 2 as 15 hence task is impossible
08.12.2014 13:25
Unfortunately, that doesn't work since the highest power of 2 dividing $17 \times 18 \cdots \times 32$ is 16, not 15.
25.11.2015 08:36
Fairly simple I can't believe this one's an RMO problem. Product of all numbers gives even power as \( 2^{16} \). So it does seem possible. However, as soon as you place a \( 32 \) in one of the grids( which becomes automatically divisible by \( 16 \) ), your best go is to fill up other three grids with the even numbers. However, now you have a remaining \( 2^{11} \) whereas you need at least a \( 2^{12} \) for dividing into three groups of at least \( 2^{4} \) .Thus, the given task is not possible.
07.06.2019 21:43
Very easy problem. PROOF BY CONTRADICTION- LET IF POSSIBLE ALL NOS CAN BE WRITTEN AS GIVEN. SO PRODUCT OF ALL NOS. ACCORDING TO GIVEN CRITERIA IS 2^16.BUT IN REALITY PRODUCT IS 2^15. CONTRADICTION. OUR CLAIM WAS WRONG.
21.07.2020 09:59
Smoothe wrote: Very easy problem. PROOF BY CONTRADICTION- LET IF POSSIBLE ALL NOS CAN BE WRITTEN AS GIVEN. SO PRODUCT OF ALL NOS. ACCORDING TO GIVEN CRITERIA IS 2^16.BUT IN REALITY PRODUCT IS 2^15. CONTRADICTION. OUR CLAIM WAS WRONG. This is $\color{red}{wrong!}$.. $\color{blue}{Correction:}$ $16=2^4$ Now, we observe, which numbers can donate a $2$ and how many do they donate.. Number $\rightarrow$ 2's Donated $32 \rightarrow 5$ $30 \rightarrow 1$ $28 \rightarrow 2$ $26 \rightarrow 1$ $24 \rightarrow 3$ $22 \rightarrow 1$ $20 \rightarrow 2$ $18 \rightarrow 1$ Now, as you can see, the total number of $2's$ donated is $16$. Therefore we have only one way to divide the numbers into four grids, i.e. by putting numbers in such way that each grid will have exactly four $2's$. But, we see, $32$ alone takes with it $5$ $2's$.. $\therefore$ Such a combination, under the given constraints, is impossible.. Q.E.D. $\square$
24.07.2024 16:41
[asy][asy] import olympiad; pair A1 = (0,0); pair A2 = (1,0); pair A3 = (2,0); pair A4 = (3,0); pair A5 = (4,0); pair B1 = (0,1); pair B2 = (1,1); pair B3 = (2,1); pair B4 = (3,1); pair B5 = (4,1); pair C1 = (0,2); pair C2 = (1,2); pair C3 = (2,2); pair C4 = (3,2); pair C5 = (4,2); pair D1 = (0,3); pair D2 = (1,3); pair D3 = (2,3); pair D4 = (3,3); pair D5 = (4,3); pair E1 = (0,4); pair E2 = (1,4); pair E3 = (2,4); pair E4 = (3,4); pair E5 = (4,4); draw(A1--A5); draw(B1--B5); draw(C1--C5); draw(D1--D5); draw(E1--E5); draw(A1--E1); draw(A2--E2); draw(A3--E3); draw(A4--E4); draw(A5--E5); [/asy][/asy] We divide the grid into $4$ boxed along the midpoint points of the square. Now let one of the box contain $32$. We have $11$ powers of $2$ left but we need at least $12$ to fill up the other boxes thus contradicting our assumption. $( \Longrightarrow \Longleftarrow)$