9
$\begingroup$

The sixteen players of a football squad, wearing shirts numbered 1 to 16, have arrived in town for a tournament. At their hotel, they are assigned 16 rooms consecutively numbered. Moreover, each of them is assigned a room with a number different from her shirt number, though a multiple of it.

What room was Daniela, the squad´s top player wearing shirt No. 9, assigned?

$\endgroup$
  • $\begingroup$ Are their room no.s in ascending order from #1 to #16? $\endgroup$ – Nautilus Jun 30 at 10:29
6
+50
$\begingroup$

I have found a smaller solution than JS1 which puts player $9$ in room

$2511$

With the following assignments

$2505$ - Player $15$
$2506$ - Player $14$
$2507$ - Player $1$
$2508$ - Player $12$
$2509$ - Player $13$
$2510$ - Player $10$
$2511$ - Player $9$
$2512$ - Player $16$
$2513$ - Player $7$
$2514$ - Player $6$
$2515$ - Player $5$
$2516$ - Player $4$
$2517$ - Player $3$
$2518$ - Player $2$
$2519$ - Player $11$
$2520$ - Player $8$

Alternatively,

We can also place player $8$ into room $2504$ and this would give the same assignment for player $9$.

Reasoning

Let us try to find solutions for smaller versions of the problem before we generalise to $16$ players.

For example, if we begin with just $4$ players and are asked to make consecutive room assignments based on the same criteria, how would we achieve it?
It turns out, that in this case, as long as one of the odd-numbered rooms in the sequence is divisible by $3$, we can achieve a valid room assignment.
For example, we can assign players $(1,2,3,4)$ to rooms $(7,6,9,8)$.
Another way to put this is that we can assign players $(1,2,3,4)$, in some order, to rooms $\big(6n+k, 6n+k+1, 6n+k+2, 6n+k+3\big)$ for any positive integer $n$, for any $k$ in the set $\{ 0, 1, 2, 3\}$

Now, let us consider the scenario where we have $8$ players.
We already know from the previous discussion that we can assign the players $2,4,6$ and $8$ simply by doubling the classes of solutions found previously. That is $(2,4,6,8)$ can be assigned to $\big(12n+2k, 12n+2k+2, 12n+2k+4, 12n+2k+6\big)$ for any positive integer $n$ and for any $k$ in the set $\{ 0, 1, 2, 3\}$. Then, we can search for the sub-cases of $n$ and $k$ for which we can fill in the odd numbers in between. Notice that, for fixed $k$, there will be a repeating pattern after every $35$ values of $n$. That is, a solution for $(n,k)$ implies a solution for $(n+35N, k)$ with $N$ a positive integer.
We can break down our analysis to look at the values of $k$ separately.
k=0
In this case, the only odd number divisible by $3$ in the range will be $12n+3$, so that is where player $3$ must be placed. This means that within the set $\{12n-1, 12n+1, 12n+5, 12n+7\}$ one must be divisible by $5$ and a different one by $7$ but the assignments cannot be made to both the first and last entries. It's easily seen that the number of ways to do this is $2\left(\binom{4}{2} - 1\right) = 10$.
The analysis is a little tedious here but can be done by hand. The $10$ values of $n$ for which this happens are $\{4, 7, 10, 13, 17, 18, 25, 27, 34, 35\}$. In particular, for any $m \geq 0$, the solutions for the $8$-player case within this class are
those rooms in the range $[420m+12n-1,\, 420m+12n+6]$ for $n \in \{ 10, 13, 17, 18, 25, 27\}$ and
those rooms in the range $[420m+12n, \,420m+12n+7]$ for $n \in \{ 4, 7, 25, 27, 34, 35\}$
k=1
The analysis in this case is very similar (there is a slight additional subtlety as $12n+9$ is also in this range which gives us access to a few more solutions), so I won't go into all the details but for any $m \geq 0$, the solutions for the $8$-player case within this class are
those rooms in the range $[420m+12n+1,\, 420m+12n+8]$ for $n \in \{ 4, 7, 25, 27, 34, 35\}$ and
those rooms in the range $[420m+12n+2, \,420m+12n+9]$ for $n \in \{ 5, 6, 13, 15, 19, 21, 28, 29, 34, 35\}$
k=2
For any $m \geq 0$, the solutions for the $8$-player case within this class are
those rooms in the range $[420m+12n+3,\, 420m+12n+10]$ for $n \in \{ 5, 6, 13, 15, 19, 21, 28, 29, 34, 35 \}$ and
those rooms in the range $[420m+12n+4, \,420m+12n+11]$ for $n \in \{ 7, 9, 27, 30, 34, 35\}$
k=3
For any $m \geq 0$, the solutions for the $8$-player case within this class are
those rooms in the range $[420m+12n+5,\, 420m+12n+12]$ for $n \in \{ 7, 9, 27, 30, 34, 35 \}$ and
those rooms in the range $[420m+12n+6, \,420m+12n+13]$ for $n \in \{ 7, 9, 16, 17, 21, 24 \}$

Now let us consider the case of $16$ players.
We already know from the previous discussion that we can assign the even-numbered players simply by doubling the classes of solutions found in the previous paragraph. Then, we can search for the sub-cases of $m$, $n$ and $k$ for which we can fill in the odd numbers in between.
A useful thing to note here is that we will be trying to assign $5$ and $15$ to odd-numbered rooms so, in our run of $16$ consecutive room numbers, there must be two which end in $5$. This means that the last digit of the first element of the consecutive room numbers must be either $0, 1, 2, 3, 4$ or $5$.
This leaves us with the following number ranges to test:
$[840m+24n-3,\, 840m+24n+12]$ for $n \in \{ 17, 27\}$,
$[840m+24n-2,\, 840m+24n+13]$ for $n \in \{ 13, 18\}$,
$[840m+24n-1, \, 840m+24n+14]$ for $n \in \{ 4, 34\}$,
$[840m+24n, \, 840m+24n+15]$ for $n \in \{ 25, 35\}$,
$[840m+24n+1,\, 840m+24n+16]$ for $n \in \{ 25, 35\}$,
$[840m+24n+2,\, 840m+24n+17]$ for $n \in \{ 7, 25, 27, 35\}$,
$[840m+24n+3, \,840m+24n+18]$ for $n \in \{ 5, 13, 15, 28, 35\}$,
$[840m+24n+4, \,840m+24n+19]$ for $n \in \{ 5, 15, 19, 29, 34, 35\}$,
$[840m+24n+5,\, 840m+24n+20]$ for $n \in \{ 5, 15, 19, 29, 34, 35 \}$,
$[840m+24n+6,\, 840m+24n+21]$ for $n \in \{ 6, 19, 21, 29, 34 \}$,
$[840m+24n+7, \,840m+24n+22]$ for $n \in \{ 7, 9, 27, 34\}$,
$[840m+24n+8, \,840m+24n+23]$ for $n \in \{ 9, 34\}$,
$[840m+24n+9,\, 840m+24n+24]$ for $n \in \{ 9, 34\}$,
$[840m+24n+10,\, 840m+24n+25]$ for $n \in \{30, 35\}$,
$[840m+24n+11, \,840m+24n+26]$ for $n \in \{16, 21 \}$,
$[840m+24n+12, \,840m+24n+27]$ for $n \in \{7, 17 \}$,
For each $m$, this is $50$ cases to check but we can start with $m=0$
In each case, it's reasonably quick to check by hand (often the cases for $13$ and $11$ can be ruled out pretty quickly). For example, $n = 34$ and $35$ appear quite frequently so we can test for primality in the range following these numbers. It turns out that, in the case $m=0$, there is no solution (although the range beginning at $363$ comes very close).
Next, we try $m=1$. Again, testing through the cases, I've found no solutions in this range.
Next, we try $m=2$. This time there are two cases which work!

These are $(m,n,k) = (2,34,8)$ and $(2,34,9)$

Addendum

JS1's solution occurs at $(m,n,k) = (4,5,3)$ and is the next smallest solution in the class listed (as far as I can tell).

$\endgroup$
8
$\begingroup$

The simple answer to this is: take number A = 1*2*3...*16. It is multiple of each of numbers shirts. Then put player 1 in A+1 room, player 2 in A+2 room and so on player 16 in A+16 room.

Explanation: if some number N is multiple of k, then N+k is as well, so all rules are preserved, rooms are consecutive, not coinsiding with each player's shirt and multiples of thie shirt numbers

P.S Almost forgot, should be nice to specify the answer, Daniela is in room Number A+9=1*2*3*...*16+9

$\endgroup$
5
$\begingroup$

The answer to this question can be solved by -

  1. Taking the LCM of all the numbers(1 to 16) and then adding to the jersey number of the players
  2. By multiplying all the numbers from 1 to 16 and then adding to the jersey number of the players.

The result will be the consecutive number of hotel rooms. In this case, if we choose the 1st approach(the LCM one), the room number of 9th player comes out to be

The Solution:

720729.

$\endgroup$
  • 1
    $\begingroup$ Oh, good answer, just multiple was first that came to my mind, but LCM is even more smart as it produces smaller numbers $\endgroup$ – Igor sharm Jun 27 at 15:21
  • 1
    $\begingroup$ I have a smaller solution: instead of adding the jersey number to the LCM, you can just as well subtract it :-) $\endgroup$ – Bass Jun 27 at 18:02
  • 2
    $\begingroup$ @Igorsharm You don't need two primes with a gap of 16 in between, because one of the players has a shirt with a 1 on it. You need three consecutive primes where the gap-sizes add up to at least 15. $\endgroup$ – Gareth McCaughan Jun 27 at 22:45
  • 1
    $\begingroup$ (I agree that finding a decent answer to this without a computer seems like an unpleasant chore, though. But maybe I'm missing some clever trick.) $\endgroup$ – Gareth McCaughan Jun 27 at 22:46
  • 3
    $\begingroup$ No hotel with that many rooms in town, @BernardoRecamánSantos? What about the one around the corner run by that nice Hilbert chap? $\endgroup$ – Gareth McCaughan Jun 30 at 13:26
4
$\begingroup$

Room 3483

3483 = 9 x 387
3484 = 4 x 871
3485 = 5 x 697
3486 = 14 x 249
3487 = 11 x 317
3488 = 16 x 218
3489 = 3 x 1163
3490 = 10 x 349
3491 = 1 x 3491
3492 = 12 x 291
3493 = 7 x 499
3494 = 2 x 1747
3495 = 15 x 233
3496 = 8 x 437
3497 = 13 x 269
3498 = 6 x 583

Method:

First, I used this comment by AxiomaticSystem:

"It's fairly easy to show that odd-numbered jerseys must reside in odd-numbered rooms. Also, Gareth's statement about primes actually holds for 17-rough numbers"

This led me to the conclusion that the room holding player 15 had to be in a room with number $30*n + 15$ (i.e. an odd numbered room divisible by 15, which only happens every 30 numbers).

With that in mind, I searched through this list of 17-rough numbers, looking at every odd multiple of 15: 15, 45, 75, 105, 135, 165, etc. I looked for a gap around the 15-multiple big enough to hold 16 numbers with only one 17-rough number in the gap (which would be used for player #1). There are barely any gaps that fit this criterion. The first possible gap was around 1965 and the odd numbers worked but the evens did not. The second possible gap was around 3495 and it worked.

BTW, I don't know if using a list of 17-rough numbers is considered using a computer. If so, you can disqualify my answer.

$\endgroup$
  • 1
    $\begingroup$ Very nice! I was pushing up a lower bound using gaps of 17-rough numbers combined with a mod-90 constraint to ensure 9 and 15 could be placed, but it was going far too slowly to get the answer so I stopped. $\endgroup$ – AxiomaticSystem Jun 30 at 13:27
  • $\begingroup$ @JS1 I will accept this answer if no one comes up with a smaller room number known to me and which also solves the problem. $\endgroup$ – Bernardo Recamán Santos Jun 30 at 21:22

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.