7
$\begingroup$

31 people are dancing in a circle formation. Each people’s age is a 2-digit number, and for each digit we know that the units’ digit is equal to the tens’ digit of the person who is in the clockwise position, while the tens’ digit is equal to the units’ digit of the person who is in the counter-clockwise position. Any 2 neighboring digits are different. Check if the product of all 31 ages can be a perfect square.

I don’t know how to start :(

All I can tell is that the digits appear in pairs: If we have, for example 31 digits, $d_1, d_2, \ldots, d_{31}$, then the ages are: $$ 10 \cdot d_1+d_2, 10 \cdot d_2+d_3, \ldots, 10 \cdot d_{31}+d_1 $$ and obviously the product is $(10 \cdot d_1+d_2) \cdot (10 \cdot d_2+d_3) \cdots (10 \cdot d_{31}+d_1)$. But I don’t know how to continue.

$\endgroup$
  • 1
    $\begingroup$ Does "Any 2 neighboring digits are different" mean that $d_i\neq d_{i+1}$ or that $10d_{i-1} + d_i\neq 10d_i + d_{i+1}$? $\endgroup$ – Arthur Jan 9 '18 at 13:11
  • $\begingroup$ @Arthur: The first one. Maybe I have not expressed it correctly. $\endgroup$ – Eduardo Juan Ramirez Jan 9 '18 at 13:49
  • 1
    $\begingroup$ It basically just means that no one has an age divisible by $11$, then. That's a different way of saying it that may be less ambiguous. $\endgroup$ – Arthur Jan 9 '18 at 13:55
  • $\begingroup$ The statements about units same as 10 clockwise and 10s same as unit cclockw are equivalent and redundent. This is units are $d_1 ... d_{31}$ and the ages are $10d_k + d_{k+1}$ $\endgroup$ – fleablood Jan 9 '18 at 19:44
5
$\begingroup$

It's possible. To restate the goal, we want a cycle of digits $d_1 \to d_2 \to d_3 \to \ldots \to d_{31} \to d_1$, such that $$ (d_1 d_2) (d_2d_3) (d_3d_4) \ldots (d_{31} d_1) $$ is a perfect square. We can build this up by combining small cycles. First,

$$2 \to 7 \to 2$$

is a nice move, as it gives $27 \cdot 72$ -- dividing out squares, we have $3 \cdot 2 = 6$. We can also do the move $$ 2 \to 5 \to 2 $$ which is $25 \cdot 52$, or just $13$ remaining. And we also have $$ 2 \to 6 \to 9 \to 2 $$ which is $26 \cdot 69 \cdot 92$, or $2 \cdot 13 \cdot 3 \cdot 23 \cdot 23 \cdot 4$, or just $6 \cdot 13$. So all of these together give a perfect square cycle of total length $2 + 2 + 3 = 7$: $$ \underbrace{2 \to 7 \to 2 \to 5 \to 2 \to 6 \to 9 \to 2}_{\text{perfect square cycle}}. \tag{a} $$

But that's not good enough -- we need another way of getting a perfect square, because cycles of length $7$ can't add up to get total length $31$. So here's another cycle: $$ \underbrace{2 \to 4 \to 2 \to 1 \to 2}_{\text{perfect square cycle}}. \tag{b} $$ Just to verify this, we have $24 \cdot 42 \cdot 21 \cdot 12$, dividing out squares and factoring $6 \cdot (6 \cdot 7) \cdot (3 \cdot 7) \cdot 3$, so everything ends up squared. This time, the cycle has length $4$. (This was a bit more complicated than necessary. We could just have done $2 \to 5 \to 2 \to 5 \to 2$, or $2 \to d \to 2 \to d \to 2$ for any $d$, for that matter.)

Then we are done: by starting from $2$ and traversing cycle (a) one and cycle (b) six times, the total length is $$ 7 + 4 + 4 + 4 + 4 + 4 + 4 = 31. $$

Some intuition (if you know graph theory)

The whole length $31$ cycle can be thought of as a cyclic path in the complete graph with $9$ vertices, where each vertex is a different digit. The path of length $31$ then decomposes into a bunch of cycles of small length ($\le 9$). The procedure to decompose into small cycles is as follows: for any cycle of length greater than $9$, it must repeat some vertex twice; therefore, it splits into two cycles from the repeated vertex.

So the goal is basically to find a bunch of small cycles whose total length is $31$, and which multiply to a perfect square. Hence, my approach was to start looking for small cycles and what they multiply to, and then try to get them to cancel out.

$\endgroup$
  • $\begingroup$ 6005: You are brilliant, thank you! I didn't quite understand the intuition part, but the first part is very explanatory! $\endgroup$ – Eduardo Juan Ramirez Jan 9 '18 at 20:06
  • $\begingroup$ @EduardoJuanRamirez Glad to help. The intuition part is mainly if you happened to know graph theory :) $\endgroup$ – 6005 Jan 9 '18 at 20:46
0
$\begingroup$

D'oh

This is easier.

Any chain $ab,ba,ab,ba$ of length $4$ will have a perfect square product.

Any chain of $ab, bc, cd, ..... , za$ repeated an even number of times will have a perfect square product.

And there are two digit perfect squares.

The only issue is the even length chains $ab,ba,ab,ba$ end with the same digit they started, and the even number of $ab, bc, cd, ..... , za$ chains must imediately follow each other.

So we need $31 = 4*k + 2j + m$

$31 = 4*7 + 3$

$= 4*4 + 3*4 + 3$

$= (4+1+4+1+ 4+1 + 4)+ 3*4$

So people aged:

$ab,ba,ab,ba$

$ac$

$cd,dc,cd,dc$

$ce$

$ef,fe,ef,fe$

$eg$

$gh,hg,gh,hg$

$hi,jk,ka$

$hi,jk,ka$

$hi,jk,ka$

$hi,jk, ka$

Where $ac,ce,eg$ are perfect squares.

This will do it.

Let $ac = 16; ce=64; eg= 49$ and so long as we can find six able bodied people in their nineties (well, only 4 really) we have it.

Then four people age $6d,d6,6d,d6$.

Then a person aged $64$.

Then four people aged $4f,f4,4f,f4$

Then a person aged $49$.

Then we have four people aged $9g,g9,9g,g9$. (Two nonagenarians is feasable. Good for them).

That's 19 people.

The remaining $12$ are $4$ groups of people aged $9h,hi,i1$ (Okay we have six nonagenarians. A little unlikely but ... heck mor power to them.)

So the product of the ages are $1b^2*b1^2*16*6d^2*d6^2*64*4f^2*f4^2*49*9g^2*g9^2*9h^4*hi^4*i1^4$ is a perfect square.

===== old answer =====

Let $d_1, d_3,..... d_{29} = a$.

Let $d_2, d_4, .... d_{30} = b$.

Let $d_{31} = c$

Ages $d_1d_2,d_3d_4,.....d_{29}d_{30} = 10a + b$

Ages $d_2d_3, d_4d_5,....d_{28}d_{29} = 10b + a$

Age $d_{30}d_{31} = 10b + c$

Age $d_{31}d_1 = 10c + a$.

Product of their ages ard $(10a+b)^{15}(10b+a)^{14} (10b + c)(10c+a)$

We need to find three digits where $(10a + b)(10b+c)(10c + a)$ isa perfect squares.

That shouldn't be hard.

$\endgroup$
  • 2
    $\begingroup$ Unless it is hard.... $\endgroup$ – fleablood Jan 9 '18 at 20:30
  • $\begingroup$ How about 17, 75, 51? (Found by brute-force search) $\endgroup$ – awkward Jan 10 '18 at 13:03
  • $\begingroup$ $A_{1,3,5,....,29} = 75; A_{2,4,6,...,28} = 57; A_{30}=51; A_{31}=17$ then $\prod A_i = 75^{15}*57^{14}*71*17 = 75^{14}*57^{14}*75*51*17 = 75^{14}*57^{14}*(3*5^2)*(3*17)*17 = 75^{14}*57^{14}*3^2*5^2*17^2$. Yup... that will do it. $\endgroup$ – fleablood Jan 10 '18 at 18:08
  • $\begingroup$ My original mistake was thinking if $A_{1,3,... ,29} = ab$ there would be $14$ of them, not $15$ so then we'd need $bc$ and $ca$ multiply to a perfect square, which would have been very easy. $\endgroup$ – fleablood Jan 10 '18 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.