For an integer \( n \geq 3 \), John has \(n-1\) cards numbered from 2 to \(n\) and he wants to put them in two boxes according to the following rule:

If \(a\) and \(b\) are the numbers of two cards and \(b \mid 2^{a}-1\), then the cards with these numbers are in different boxes.

What's the biggest number \(n\) for which it is possible for John to keep following this rule?

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewest@Jon Haussmann You're right. I made a mistake at n=7. Do you think there's any better way to prove this? I can't come up with anything other than this brute force method.

Log in to reply

I don't see any other way. And it's pretty easy to go up to \(n = 7\), so I wouldn't call it brute force.

Log in to reply

I can only get up to \(n = 6\).

Call the boxes box A and box B. The number 2 has to go somewhere, so let's just put it in box A.

Since 3 divides \(2^2 - 1\), the number 3 has to go in box B. Since 3 divides \(2^4 - 1\) and \(2^6 - 1\), the numbers 4 and 6 have to go in box A. Since 5 divides \(2^4 - 1\), the number 5 has to go in box B. Thus, we can place the numbers 2, 3, 4, 5, and 6. Furthermore, the placement of these numbers is forced, i.e. this is the only possible way. (We can swap the numbers in box A and box B, but it's basically the same.)

Now, 7 divides \(2^3 - 1\) and \(2^6 - 1\), so we cannot place the number 7 in either box. This means \(n = 6\) is as high as we can go.

Log in to reply

I tried this until n=15 and it failed there so I think the answer is 14 but it isn't a very elegant proof (brute force never is ahah)

Log in to reply