9
$\begingroup$

2022 cards are arranged on the table in front of us. Each card shows a number that we can see. For each of the numbers from 1 to 2022 inclusive, there is exactly one card that depicts it. We have the right to take cards from the table at our will, as long as we observe the following two restrictions:

  1. We are not allowed to hold cards whose numbers differ by 4
  2. We are not allowed to hold cards whose numbers differ by 7

Example: if we have taken a card with the number 10, then we are not allowed to take the cards with numbers 6 and 14 (from the first restriction) and the cards with numbers 3 and 17 (from the second restriction).

What is the maximum number of cards that we can take from the table?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

I can get

920 cards.

My thought process is

I can take 5 out of every 11 consecutive cards. If I take cards (1, 3, 4, 6, 9), and then (12, 14, 15, 17, 20), etc. I will have taken 915 of the first 183*11 = 2013 cards. I can then take (2014, 2016, 2017, 2019, 2022) to bring the total to 920.

I believe this is the maximum because

choosing a card eliminates four other cards from being chosen (ignoring the edge cases). An optimal strategy would seem to be picking subsequent cards which "duplicate" as many eliminated cards as possible. So for example, if we pick the card numbered 10, we've eliminated cards 3, 6, 14 and 17. For the next choice, we'd like to pick something that also eliminates as many of (3, 6, 14, 17) as possible, to minimize the number of new cards we're eliminating. It's easy to see that we can choose a number that eliminates two of the same cards as our previous choice by picking a number 3 greater, e.g. picking card #13 in this case, since it also eliminates cards 6 and 17.
It's also easy to see that we can repeat patterns of 11 cards. So by picking every third card, we end up with four cards in a group of 11, plus a gap where we can choose a fifth card.

I've made two pictures to help illustrate what's happening.

1 This shows the first step of choosing every third card (blue spaces are cards we've chosen, pink spaces are cards we cannot choose by virtue of the cards we've already chosen). 2 This shows the completed pattern once we've chosen a fifth card.
And since 2022 is 9 mod 11, we want to align the pattern of choices so that all 5 cards are in the first 9, so that we can get 5 of the last 9 - i.e. the pattern pictured in my links above might have us choose cards 1, 2, 4, 7, 10, ... but then we would only get 4 of the last 9, leaving us with a total of 919 instead of the optimal 920.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Do you know if this is optimal? Or is it just the best you've found so far. $\endgroup$
    – fljx
    May 25, 2022 at 21:02
  • $\begingroup$ I believe it's optimal, I've edited my answer with an explanation. $\endgroup$
    – SQLnoob
    May 25, 2022 at 21:38
  • $\begingroup$ I wrote a simulated annealing method that finds solutions for different modulo. Modulo 11 that you are using seems to be the best and I cannot beat your score. So perhaps it is optimal. $\endgroup$
    – Dmitry Kamenetsky
    May 26, 2022 at 8:15
  • 1
    $\begingroup$ I manually select the modulo M. Then I choose which of the cards from 0 to M-1 I take. I score this sequence. The scoring function maximizes the number of cards taken and then subtracts a large penalty for each collision (differences of 4 and 7). It then computes how this sequence would score on the full set of cards from 1 to 2022. This is all run inside simulated annealing, where each move involves selecting/deselecting a card within the sequence. $\endgroup$
    – Dmitry Kamenetsky
    May 26, 2022 at 11:33
  • 1
    $\begingroup$ To complete your argument, simply show that you cannot choose more than 5 of any 11 consecutive cards, because you cannot choose two adjacent cards in the cycle 1-8-4-11-7-3-10-6-2-9-5-1. A simple counting argument then shows you've achieved the upper bound. $\endgroup$
    – Magma
    May 26, 2022 at 23:05
3
$\begingroup$

Taking

1,2,3,4, then 12,13,14,15, ... 2014,2015,2016,2017 yields 736 cards.

I will continue this later when I get home to see if there is a clever way to space them so more cards can be taken.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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