11
$\begingroup$

Take the 4 aces, 4 twos, 4 threes, and 4 fours from an ordinary deck of playing cards.

Is it possible to place all 16 cards in a row on a table so that there is precisely 1 card between any 2 successive aces, 2 cards between any 2 successive twos, 3 cards between any 2 successive threes, and 4 cards between any 2 successive fours?

Can an analogous placement be achieved if the 4 fives are included?

$\endgroup$
4
  • 1
    $\begingroup$ Do you possibly mean any 2 "neighboring" aces? As it stands, this is impossible since _A_A_A_ (where blanks represent other cards) will not have precisely 1 card between the 1st and 3rd aces, etc. $\endgroup$
    – Quintec
    Dec 3, 2019 at 1:57
  • $\begingroup$ @Quintec Yes, I do! Does my clarification clarify? $\endgroup$ Dec 3, 2019 at 2:00
  • $\begingroup$ Yep, makes sense now. $\endgroup$
    – Quintec
    Dec 3, 2019 at 2:02
  • $\begingroup$ There isn't a tag for pigeonhole-principle? $\endgroup$
    – smci
    Dec 3, 2019 at 10:53

5 Answers 5

4
$\begingroup$

An answer for 5s (updated)

The only pattern to fit both 4s and 5s into 20 spaces is 45xxx4x5xx4xx5x4xxx5. Now it's clear that in the two xxx spaces there cannot be more than one 2 or 3, and likewise the aces obviously cannot be in both spaces (since 4 aces require 1x1x1x1 pattern, so they have to fit in 7 slots). So we get a contradiction, and therefore the solution is impossible.

$\endgroup$
2
  • $\begingroup$ Great! Any hope of a solution with more cards? $\endgroup$ Dec 3, 2019 at 11:58
  • $\begingroup$ @BernardoRecamánSantos I've written a script for checking it. At least, it seems impossible with 6s and 7s too. $\endgroup$
    – trolley813
    Dec 3, 2019 at 12:00
14
$\begingroup$

I claim that no arrangement is possible in the case with cards ace through four.

Note that

_A_A_A_A_ (_ is any other card)

must be part of the arrangement. Now consider two cases:

  • the row starts and ends with aces - this is obviously not possible, since that arrangement would only hold 7 cards, and we require 16.

  • there are cards to the left and right of the aces.

If so, what could the card to the left of the first ace (WLOG) be? It cannot be a 2 or 4, since there are aces in the positions where another 2/4 would go.

Consider the case of 3:

3A_A3A_A

Note that the middle blank must also be a 3 in this case since 2 and 4 are impossible as shown above.

Now consider the remaining middle blanks - the only possible cards to fit there within the constraints are threes, which would invalidate the already placed threes.

Therefore, we have shown by casework that such an arrangement is impossible. $\square$

$\endgroup$
2
  • $\begingroup$ All 16 cards must be placed on the table. $\endgroup$ Dec 3, 2019 at 2:17
  • 6
    $\begingroup$ @BernardoRecamánSantos Yes, but I have tried to show that it is impossible no matter what due to a subset of the cards, irregardless of where the rest go. $\endgroup$
    – Quintec
    Dec 3, 2019 at 2:29
9
$\begingroup$

A similar answer to Quintec's (asserting that it is impossible):

Consider that you only have 12 cards that are not a 4, and that you need 12 total cards between the 4s. So the entire arrangement must look like

4 _ _ _ _ 4 _ _ _ _ 4 _ _ _ _ 4

As per Quintec's observation, somewhere in there we must have

_ A _ A _ A _ A _

But you can see that there are only two options for where to put the aces now, and they're symmetric, so we might as well pick this one:

4 _ A _ A 4 A _ A _ 4 _ _ _ _ 4

Finally, let's try to place the 2s. They require this pattern:

_ 2 _ _ 2 _ _ 2 _ _ 2 _

Simple trial and error shows that there's no place to put these.

$\endgroup$
4
  • $\begingroup$ Can this argument be applied to longer sequences of cards? $\endgroup$ Dec 3, 2019 at 3:06
  • 3
    $\begingroup$ No, but there is an argument using the largest-valued card (say N) and the second-largest valued card N-1. The N cards must span the whole arrangement, and the N-1 cards need 4N-4 spaces within their span (inclusive). That means they must start in position 1, 2, 3, or 4 in order to fit. But each of these starting spaces causes a conflict with one of the N cards. $\endgroup$
    – hdsdv
    Dec 3, 2019 at 3:36
  • 3
    $\begingroup$ @hdsdv The assertion that "The N cards must span the whole arrangement" is false for N > 4. The width of the N cards is 3N+4 whereas the width of the whole arrangement is 4N. $\endgroup$
    – hexomino
    Dec 3, 2019 at 10:51
  • $\begingroup$ Ah, yes - you're right. $\endgroup$
    – hdsdv
    Dec 3, 2019 at 11:48
6
$\begingroup$

As claimed above by other users, the arrangement is imposible with four sets of four cards. The earliest solution occurs for four sets of cards 1 to 24, for which there are three solutions. These are known as Langford Quads and are described at John Miller's excellent blog on Langford's Problem.

These are Richard Noble's three solutions.

$\endgroup$
2
  • 1
    $\begingroup$ It also says there that there is proof that N must be 0 or 7 modulo 8 (i.e. the other cases are definitely impossible, but that does not necessarily mean there are solutions when N is 0 or 7 mod 8). I can't quite prove that myself, but I can easily show that N must be 0 or 3 modulo 4. $\endgroup$ Dec 4, 2019 at 15:07
  • 3
    $\begingroup$ I am new here. I just edited my Langfords page regarding Quads. I noticed that column in the Solutions table was incomplete. The number of solutions for Quads goes like this: L(4,17)=1, L(4,18)=1, L(4,19)=5, L(4,20)=14. Strangely, L(4,24)=3. I am sending these actual sequences to Freddy for his edification. He can post them here if there is interest. The "condition of solvability" on may page is suspect. Sorry for any confusion!! I've flagged it on the page, and will continue a literature search on this condition. $\endgroup$
    – jem
    Feb 2, 2020 at 8:18
0
$\begingroup$

Solution with any numbers of cards:

Short version (as many already wrote) no.
Explanation:
Let's say you use cards from Ace(1) to n.
The only possible way to place the nCards is this:
n _ ... _ n _ ... _ n _ ... _ n - with n times _ in between
now you have n places to put the n-1Cards in between any 2 nCards.
The Problem is, that you need at least (n-1+2) spaces in between any 2 nCards to fit 2 of your n-1Cards in one section (n-1 in between those n-1Cards and 2 spaces for the cards itself.)
That forces you to put your next n-1Card into the next section - but there are only 3 sections while you need to place 4 n-1Cards

$\endgroup$
1
  • $\begingroup$ There are 4n cards all together, so apart from the 3 sections of n cards, there are also n-4 further places on the outside, to the left of the leftmost n-card and to the right of the rightmost n-card. Therefore you do not need to put two (n-1)-cards in the same section between the n-cards. $\endgroup$ Dec 4, 2019 at 14:03

Your Answer

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

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