The unsolved math problem inspired by a children's game
Вставка
- Опубліковано 21 чер 2024
- While observing his child play with toy blocks, C. Dudley Langford invented a puzzle that is still unsolved to this day! Special thanks this month to: Daniel Lewis, Kyle, Lee Redden, Mike Robertson. Thanks to all supporters on Patreon! / mindyourdecisions
0:00 Problems
3:21 Answers
6:29 Impossible
10:17 Necessary
14:24 Sufficient
18:13 Unsolved
Painting in preview
en.wikipedia.org/wiki/Toy_blo...
Interview question
math.stackexchange.com/questi...
Susam Pal blog post
susam.net/blog/langford-pairi...
Vamshi Jandhyala post
vamshij.com/blog/linear-optim...
DataGenetics post
datagenetics.com/blog/october3...
Yurii Lahodiuk post
lagodiuk.github.io/computer_sc...
Guardian Alex Bellos
www.theguardian.com/science/2...
Langford pairing
en.wikipedia.org/wiki/Langfor...
OEIS Number of solutions
oeis.org/A014552
Counting Skolem-Langford sequences
arxiv.org/abs/1507.00315
Subscribe: ua-cam.com/users/MindYour...
Send me suggestions by email (address at end of many videos). I may not reply but I do consider all ideas!
If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.
If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.
Book ratings are from January 2023.
My Books (worldwide links)
mindyourdecisions.com/blog/my...
My Books (US links)
Mind Your Decisions: Five Book Compilation
amzn.to/2pbJ4wR
A collection of 5 books:
"The Joy of Game Theory" rated 4.3/5 stars on 290 reviews
amzn.to/1uQvA20
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" rated 4.1/5 stars on 33 reviews
amzn.to/1o3FaAg
"40 Paradoxes in Logic, Probability, and Game Theory" rated 4.2/5 stars on 54 reviews
amzn.to/1LOCI4U
"The Best Mental Math Tricks" rated 4.3/5 stars on 116 reviews
amzn.to/18maAdo
"Multiply Numbers By Drawing Lines" rated 4.4/5 stars on 37 reviews
amzn.to/XRm7M4
Mind Your Puzzles: Collection Of Volumes 1 To 3
amzn.to/2mMdrJr
A collection of 3 books:
"Math Puzzles Volume 1" rated 4.4/5 stars on 112 reviews
amzn.to/1GhUUSH
"Math Puzzles Volume 2" rated 4.2/5 stars on 33 reviews
amzn.to/1NKbyCs
"Math Puzzles Volume 3" rated 4.2/5 stars on 29 reviews
amzn.to/1NKbGlp
2017 Shorty Awards Nominee. Mind Your Decisions was nominated in the STEM category (Science, Technology, Engineering, and Math) along with eventual winner Bill Nye; finalists Adam Savage, Dr. Sandra Lee, Simone Giertz, Tim Peake, Unbox Therapy; and other nominees Elon Musk, Gizmoslip, Hope Jahren, Life Noggin, and Nerdwriter.
My Blog
mindyourdecisions.com/blog/
Twitter
/ preshtalwalkar
Instagram
/ preshtalwalkar
Merch
teespring.com/stores/mind-you...
Patreon
/ mindyourdecisions
Press
mindyourdecisions.com/blog/press - Наука та технологія
While I personally love this question, I’ve been in the tech industry for 20 years and if this question came up during an interview I would leave immediately
i would fart before i left.
@@JohnLeePettimoreIII💀
I've been in many interviews and some of them do indeed get pretty ridiculous. I once had an interview where I was asked some question about the arrival time of trains or something. I only remember it being a ridiculously difficult problem. I couldn't figure it out but they claimed that they did calculations like that all the time. The job had nothing to do with trains.
tech jobs interviews require you to solve problems like these and then after they hire you, you only solve simple trivial problems everyday
I gave a simple math problem in my interview, and my expectation was that people would refuse to do it. It filters out people who would say "not my job" or "can't do it," which is very important.
Almost all jobs are about management systems; the jobs I hired for weren't.
So, such problems effectively show what will be expected on the job.
You can tell a senior developer that you are solving unique challenges, and they will think that you are doing about the same as the next company and that they can reuse knowledge of what they did during their career. Except that they can't.
And if you tell them explicitly, as in, "This job will require you to analyze new problems and find novel solutions, so most of the solutions you already know don't apply," they think you don't know what you're talking about!
So, when using such items, you should do it knowingly. Misuse will have you ditch the best management system programmers!
i think there is a nice way to show the “impossible”/“necessary” part of this. Instead of labeling the spaces as 1,2,3,…2n, just label them odd and even. for any odd k in {1,2,…n} the ‘k-labeled’ blocks are either both in even spaces or both in odd, for any even k there is one ‘k-labeled’ block in an even space and one in an odd space. If the number of odd numbers in {1,2,…n} isn’t even then you can’t fill an identical number of even and odd spaces. Since there is an identical number of even and odd spaces from 1 to 2n, the necessary condition is simply: “the number of odd numbers in {1,2,…n} must be even”, or restated: n = 0 or 3 (mod 4)
Solved it the same way, but with coloring black and white
@@DmitDmit1 IKR. When in doubt in visual/spatial/positioning puzzles, just paint it like a checkerboard lol. Bam, 4k+2 and 4k+1 are impossible.
@@DmitDmit1Same here. The checkerboard approach very often shows easy answers.
@@DmitDmit1Exactly.
This property of odds also appears to be used in Egyptian Multiplication
I like how you just showed the solution to the first one when presenting the question
Presh really knows how to make these complex math problems look so easy.
I don't know about easy but understandable anyway.
unless the job is a math-heavy position, there is absolutely no reason this question should be in *_ANY_* interview.
how long will this candidate spend on an impossible and fruitless task before either proving it impossible or moving on to something productive?
Can they acknowledge when something is beyond their ability quickly?
The last thing the interviewer wants is for you to already know the problem and quickly proving it impossible is a close penultimate because it reveals little of your character or decisionmaking/prioritising under pressure.
@@imb0wcile Doesn't that mean that if I already know the solution to the problem and that the interviewer is really evaluating how I handle failure I can *pretend not to know* and come out looking better than if I state the solution? Seems like a terrible way to evaluate someone's capabilities if it incentivizes hiding my prior knowledge from the interviewer.
@@bigboi1004 Anyone can lie and pretend and fakeit in an interview. the incentive is already there.
If you happen to know an answer and are sure of what the interviewer is looking for then good luck to you i guess.
you can have these questions in a programming interview
Maths is the only subject which I have found without any exceptions.There is always a reason behind everything in Maths which you can know if you try to.Maths is deep in my heart and I am trying to dig it out with my mind.❤
Chemistry also does not have exceptions it is just that you need to study quatum physics first to understand the reasons which are stated as exceptions
Does physics have exceptions?
@@henriquepereira2811 yes but i think he did not mean it?
I said, "which I have found".As a student, you can explore maths enough to clear all your doubts without any exceptions but you can't do the same with chemistry or any other subject as you have to study quantum physics or be the best expert of that subject.That's what I meant.
@@LegendaryBea Just ask yourself-How much you know chemistry without exceptions?
This video was really well done Presh. Good lecture!
your illustrations are world-class!
When I first looked at the video and saw it was 20 minutes, I thought "OMG." But the puzzle, the generalization, the proof and how it was outlined was fascinating. Thank you for sharing.
Hi Presh - You added a few extra steps for yourself by not using the arithmetic series summation formula to its full potential. It doesn't require that the series starts with 1. So at 9:03 you could have done 5*8/2 and at 11:39 you could have done n(n+3)/2.
This blocks arranging puzzle reminds me of a classic P = NP problem. It sounds like it has to be NP complete because for large n, it seems challenging to find ONE solution (never mind ALL solutions) but once you have a solution it's VERY easy to verify it's correct!
When I saw the teaser for this video, my thought would be 'the only thing impossible would be the person who wrote this question still having a job.' I only watched this video to see if the actual question was phrased even slightly better. Nice puzzle once it was well explained.
I also like this channel, and understand that the insertion of ads is probably controlled by UA-cam, so I pose the following math question: When does the ration of content time to commercial time become small enough that most people will go read a book? The answer is a probability for each individual, of course. For me, I’m off to read a book.
More observations can be made like
In the final solution nth digit can never be next n+1 digit
Like the first 4 can never be just right to 5,otherwise the other 4&5 position will overlap, and similarly the second 4 cannot be left of 5
Similarly for all the numbers
Another thing that for 2n boxes the coordinate of first n digit can only be from 1 to n-1 box, while first (n-1)th digit can have position from 1 to nth box, and so on
With these conditions we can work out the max possible no of solutions
I like the idea of positions overlapping, or blocks merging to become one. How would we number such a position or block? Well I suggest if two 1s are one block apart, then two 0's are no blocks apart, so side by side. If they got even closer so they overlap to become one, then I guess the number would be -1. Thus blocks numbering -1 0 1 2 3 4 -1 0 1 2 3 4 could be arranged -1 3 4 0 0 3 2 4 1 2 1.
@@chrisg3030 I used this idea to try to limit total possible solutions
Like the first nth digit can have coordinates from 1 to n-1, first (n-1)th digit can have coordinates from 1 to n...... digit 1 can have coordinates from 1 to 2n-2.
So total number of possible places for nth digit are n-1, for (n-1)th digit possible places are n, but it cannot be in the position of nth digit or just right to it so possible places are (n-2), and so on for all other digits, but this is including reversal so we divide total permutations by two,
So max possible solutions are (n-1)[(n-2)^(n-1)]/2
18:58 instantly reminded me of the list of number of exotic spheres for n dimensions. Eerily similar but not the same.
It also seems to work with negative numbers. -1 has the same number of spaces as 0 (the order is swapped) and you can have a sequence with "-1,-1" (3 mod 4) or "0,0" (0 mod 4) or "-1,-1,0,0" if the 0 is included.
You could also have the range -2 to +2 as so:
-1,-1,-2,1,-2,1,2,0,0,2
Two blocks numbered 0 should have 0 blocks between them, so sit side by side in any re-arrangement, so 0,1,2,3,4,0,1,2,3,4 becomes for example 3,4,0,0,3,2,4,1,2,1
-1 to me means the blocks get even closer and merge into one. Thus -1,0,1,2,3,4,-1,0,1,2,3,4 would be solved with just one block numbered -1, such as 3,4,0,0,3,2,4,1,2,1,-1
Great ! One of your best !
Your channel is the best 👍
We could thin about the solutions , going in the "straight line" (one dimension) now try it going up (including diagonals) 2 dimensions, do the possible solutions change ? what MOD is involved, then have the net cube (external faces 3 Dimensions, ? would going through the cube be 4dimensions or a less restricted 3 dimensions ?
Looks like some challenges for children but in fact difficult aa hell
Is there at least some nice function that correlates pretty well with the "number of solutions" sequence's nonzero values? Or maybe separate functions for the 3 mod 4 & 0 mod 4 cases?
Looking at the table at 19:10 , if we call w(n) the number of solutions for 2n blocks, I notice that for n = 4k,
w(n)/w(n-1) ≈ n/2 ,
at least when n > 8 . And I suspect that this pattern will be even more true for much larger n.
Also note that for n = 4k,
w(n+3)/w(n) ≈ (n+1)(n+2)(n+3)/(2^3) .
So I suspect that the non-zero values of w(n) may roughly match the function n!/(2^n) .
Brilliant!
I didn't wanna think so I did the original (3 blocks) visually and pretty quickly got the answer. And then he added on even more difficulty.
You lost me at the ceiling😅
I think, this is the first time (that I know of) that Presh has pulled a "the proof is left as an exercise for the reader" at the 18:01 mark! 😂
my first thought is parity: like how the 3's are both either on odd or even numbered squares. so 2 and 4 are both on different squares meannign theres 3 odd squares and 3 even squares left and since the remaining 3 are all sets that go on the same type of square making this impossible as the number of squares left arent even. this makes it so that from 4 and onwards to get it back to a possible number you need to first add the same parity blocks (+1) add the opposite parity blocks (+2) and finally the same parity again (+3) and from here you can add another set of opposite parityh blocks and it will also be possible then have to repeat it to find more possibilities so it works for numbers 4x and 4x - 1 where x is an integer.
Love to see 2+3+4+5+6 "simplified" to 6(7)/2-1 instead of just writing 20, lol.
This is an interesting puzzle, but I would like to know the basis for identifying it as an "interview question." Is some company actually presenting this question to job candidates? If so, which company? And which part(s) of the problem? The ones that Presh had to carefully research and script for this video? We're supposed to believe that job applicants are asked to do that extemporaneously? Are they also told, "If you want this job, please come up with a fresh proof of the Pythagorean Theorem in the next five minutes"?
This is a good way to learn how the candidate thinks. Are they organized, systematic, creative? How do they approach the question? Do they seek analogies? Do they reach for equations or do they describe visual/geometric methods? That becomes clear in just a five minute chat!
@robertarvanitis8852 Fine, but you didn't answer either of my questions. Which company or companies actually uses this problem in interviews? And which parts of the problem are used?
@@j.r.1210 I use open-ended questions in all sorts of situations. To see which way a person goes, what interpretation they go if there are multiple meanings. To get a sense of someone is more s thinker or a feeler. You seem to prefer clear, orderly frames. How do you perceive ambiguity? Occasion to clarify? Or opportunity?
@@robertarvanitis8852 you already know that ambiguity is kryptonite to them, lololol
Trephining, with your pseudonym, you should know: have an open mind, not a hole in the head
1 and 2 are not surprising as they are too small, but 5 and 6 actually were surprising.
4:02 also notice that by mirror symmetry your two ways of placing the 3 block are the same. So only one starting point
3:20
2 3 1 2 1 3
I found this in 20 seconds by trial and error. However, I expect the larger puzzles to be more difficult.
An alternative game with an _odd_ number of blocks and slightly different rules can be defined:
Suppose we have (2n+1) blocks, numbered
0, 1, 1, 2, 2, 3, 3, ..., n, n
The goal is to place these (2n+1) blocks into a row of consecutive positions, such that
- there are 0 blocks between the blocks numbered "1"
- there is 1 block between the blocks numbered "2"
- there are 2 blocks between the blocks numbered "3"
etc.
- there are n-1 blocks between the blocks numbered "n".
As a result,
- a block numbered "1" is paired to a block that's 1 step away,
- a block numbered "2" is paired to a block that's 2 steps away,
- a block numbered "3" is paired to a block that's 3 steps away,
etc.
- a block numbered "n" is paired to a block that's n steps away.
The block numbered "0" is paired to a block that's 0 steps away; in other words, it is paired to itself.
The solutions for n = 0, 1, 2, 3, 4 are:
0 : (1 solution)
[0]
0,1,1 : (2 solutions)
[0 1 1] or [1 1 0]
0,1,1,2,2 : (2 solutions)
[1 1 2 0 2] or [2 0 2 1 1]
0,1,1,2,2,3,3 : (6 solutions)
[2 0 2 3 1 1 3] or [3 1 1 3 2 0 2]
[2 3 2 0 3 1 1] or [1 1 3 0 2 3 2]
[3 0 2 3 2 1 1] or [1 1 2 3 2 0 3]
0,1,1,2,2,3,3,4,4 : (18 solutions)
[3 1 1 3 4 2 0 2 4] or [4 2 0 2 4 3 1 1 3]
[4 2 3 2 4 3 0 1 1] or [1 1 0 3 4 2 3 2 4]
[4 2 3 2 4 3 1 1 0] or [0 1 1 3 4 2 3 2 4]
[3 4 2 3 2 4 0 1 1] or [1 1 0 4 2 3 2 4 3]
[3 4 2 3 2 4 1 1 0] or [0 1 1 4 2 3 2 4 3]
[2 4 2 3 0 4 3 1 1] or [1 1 3 4 0 3 2 4 2]
[3 4 0 3 2 4 2 1 1] or [1 1 2 4 2 3 0 4 3]
[4 1 1 3 4 2 3 2 0] or [0 2 3 2 4 3 1 1 4]
[0 4 1 1 3 4 2 3 2] or [2 3 2 4 3 1 1 4 0]
Note that when this game is played with a row of 2(n-1) positions and without the 0, 1, 1 blocks, it is equivalent to the "Langford sequence" game in the video. The absence of the 0 block and the "11" pair, which can both potentially be placed "outside" the other blocks, makes that all pairs in any Langford sequence are always entangled with eachother.
And of course another interesting game variant is created if we modify this game by having the blocks arranged in a circle instead of a straight line.
Yes, arranging blocks in a circle produces interesting results. Using Presh's solutions we see that for n blocks, the two numbered n-1 are in opposite positions on the circle. When the sequence pairs start with two zero's (unlike yourself, in compliance with Presh's rule that the quantity of blocks between two n's is always equal to n so zero's must be side by side, 0 0) then the two numbered n are opposite.
If the mathematician never saw his child playing with wooden blocks...
Checkerboard coloring. 1s, 3s, and 5s will take two of the same color, while 2s and 4s will take one of each color. At least two of 1s, 3s, and 5s will be on the same color, by pigeonhole, so for that color we need 6 blocks, but we will only have 5.
This video is the first time I've heard someone else use the formula I discovered in college when trying to figure out how many bowling pins there are given x number of rows.
I proved the first part of n%4 using the fact that an odd gap will occupy same parity positions and an even gap will occupy different parity positions.
Hi Presh, "that guy" here :) I love the video and the puzzle but your thumbnail is wrong, it says "You have two pairs of blocks 1 to 5", which would be 4 sets of blocks :D
I think it is likely unintentional to place blank spaces into the series, because it is fully possible to arrange any group with blanks and this isn't specifically prohibited in the question, so I would go with that. Hopefully the interview would look positively at alternative thinking solutions.
Very interesting, although the solution is much simpler through the lens of parity.
First observation: There are always just as many even positions as there are odd ones.
Second observation: Even numbers must be in opposite parity positions (for instance, 2s would be in ODD even odd EVEN.) Since this adds one of each, you can think of these as cancelling themselves out as we try to balance even and odd.
Third observation: Odd numbers must be placed in the same parity position (for example, 1s could be placed in ODD even ODD.) This introduces imbalance- every odd number adds either two even positions, or two odd positions.
Since there are just as many even positions as odd positions, every odd number in an even position needs another odd number to be in an odd position. In other words, to be solvable, there must be an even number of odd numbers.
This method needs no calculation, and can be reasoned through while simply staring at the thumbnail. Neat!
We can't just say that for n>30, it is unsolved. Rather, we can say that for n>30, there must be currently at least a solution(up to reversal).
having barely any math skill or topology skills, i had a feeling the odd number was going to make an appearance.
What is the largest known Langford Pairing?
Can we fill in the missing cases if the blocks are placed in a circle rather than a line?
Certainly if you add a pair of zeros (consistencywise, separated by zero digits!) to either end then you can turn it into a circle with wrapround. E.g. the octagon 00231213, remaining the only (modulo reversals) solution. A decagon turns up as 0023421314. But there's another solution 0032412134 which doesn't work as a linear block (3s separated by 5 digits) but does as a circle (34003). No dodecagons or tetradecagons but oodles of hexadecagons.
No, we can't, because the "checkerboard" counter-argument would still be valid.
Color the 2n positions red and blue, in an alternate manner: red, blue, red, blue, red, blue etc. There will be n red positions, and n blue positions. The two blocks that are numbered "1" will occupy two positions of the same color: either [red, red] or [blue, blue] . This is also true for any pair of blocks that is numbered with an odd number ("3", "5", "7" etc.) The two blocks that are numbered "2" will occupy two positions of different color: [red, blue] or [blue, red]; and this is also true for any pair of blocks that is numbered with an even number ("4", "6", "8" etc.). Since pairs of even-numbered blocks will occupy red and blue positions in equal amounts, the positions remaining for the odd-numbered blocks are also red and blue in equal numbers (50% red, 50% blue). That means that there must be an even number of odd-numbered pairs, otherwise the number of odd-numbered pairs that occupy red positions cannot be equal to the number of odd-numbered pairs that occupy blue positions. But this means that there are no solutions for n = 1 (mod 4) and n = 2 (mod 4) , regardless of whether the positions are arranged in a line or in a circle.
(For example, for n=5 , there are three pairs with an odd number (1s, 3s, and 5s), and since three pairs is an odd number of pairs, they cannot in equal measure occupy red positions and blue positions: for example, if the 1s occupy two red positions and the 3s occupy two blue positions, then the two remaining 5s must occupy one red position and one blue position, which is not possible if there must be five positions between the two "5" blocks. So there is no solution for n=5.)
@@LemoUtan The "wraparound" solution 0032412134 is the same solution as the linear sequences 2412134003 and 3400324121 ; so it's not a solution that only works as a circle.
But what the original commenter is asking, is if there exist circle solutions for 2n blocks when n = 5, 6, 9, 10, 13, 14, etc. (in other words, when n = 1 (mod 4) or 2 (mod 4), which are those values of n that have no linear sequences as a solution). The answer to that question is "No, there won't be wraparound circle solutions either".
And adding a pair of "0" blocks doesn't repair it, as there would still be no solutions when n, which is the number on the highest numbered block(s), is equal to 1 (mod 4) or 2 (mod 4) .
@@LemoUtan An example of a "wraparound" solution that only works as a circle solution and not as a linear sequence solution, is
7 5 1 3 1 6 4 2 7 5 2 4 6 3
n=7 is the smallest number for which there exists a "wraparound" circle solution that cannot be represented as a linear sequence solution.
My mind tells me that there must be a solution for n=31/32, because it alternates between two values of n with no solution and then two values of n with a solution, with the number of solutions as n increases growing ridiculously fast. I hope that it is found, that's very fascinating. 19:37
This one made my head hurt!😂
The answer is:
You have to rearrange like this: 2, 3, 1, 2, 1, 3.
I wonder if there is some link between this problem and the five color map theorem.
Really very little, especially since I'm not sure there is a five colour map theorem. But if you want to explain what you're thinking then go for it.
@@mattc3581 I was referring to this: en.wikipedia.org/wiki/Five_color_theorem
@@billwilson6670 Fair enough, I didn't think that was something that merited being a theorum, given that the stronger four-colour theorum has already been proved for quite a while, but I guess it's a thing.
Still not really anything to do with this block puzzle though I'm afraid.
Fun fact: 6 is also impossible, but is possible again when 7 or 8. Then impossible again at 9 and 10, and so on.
For n=31 the number of solutions is so big that Presh called it unsolved factorial: unsolved!
Anyone know what the C in C. Dudley Langford stands for?
I'm reminded of the perfect numbers, where there are currently 51 known (this one having 49,724,095 digits)!
It was easy for me thanks to minesweeper tiling patterns
I believe the number of solutions for 31 is about 1.1x10^26. Anyone else have a guess?
NS31: 5.896 x 10^24
NS32: 9.7 x 10^25
So basically at 4:55 all valid non-palindromic (does not read the same forwards and backwards) Langford Pairings, will always provide a new unique distinct solution for each solution regardless of the value of n, this characteristic alone doubles each non-palindromic Langford Pairing which is probably one of the main reasons (if multiple) why valid solutions of Langford Pairings increase exponentially for each valid value of n. Valid values of n={3,4,7,8,11,12,15,16,19,20,23,24,27,28...} (however values past n>30 are unsolved as mentioned at 3:03 so I won't include those values in the set) Any value of n that is not in the set mentioned will not return a valid Langford Pairing, this set does go on indefinitely as long as you follow this pattern that for each 2 valid values of n (3 and 4 for example) the next 2 numbers (5 and 6) will automatically be invalid values, then the next 2 (7 and 8) numbers are valid, the next 2 (9 and 10) after that are invalid etc. this set pattern can be repeated indefinitely but as previously mentioned values past n
For the 1,2,3,4 puzzle you didn’t prove that was the unique solution you just found a solution.
This impossibility proves that you can't place two number 1 blocks in this way. To fill all the slots there can't be a gap.
I paused the video after each problem, solved the first two, spent a long time on the third. Got nowhere. I unpause and it says “prove it is impossible” goddammit
We have “aaaj sloesjin”
LOL 😂
Wow
I found a possible answer to the first two puzzles by myself:
1) 231213
2) 41312432
I’d just want to play with the blocks 😂
Whats mod?
I started at the thumbnail for a hot minute, thinking the colors were a deception too. After starting the video I paused and solved much more easily. The first card was the easy answer. The only one that made sense was card 4. 😂
WHO WOULD HAVE THOUGHT OF SUMMING UP the "a1, a1 + 1, a2, a2 + 2, ..." thing and the "1, ..., 2n" thing in solving this problem...
Now for 5: define a1= first position of 1, a2 = first position of 2, up to a5 = first position of 5. So a1 + 2 = last position of 1, a2 + 3 = last position of 2, up to a5 + 6 = last position of 5.
adding all first and last position gives number 10x11/2 = 55. 55 = 2sum(ai) + 6 + 5 + 4 + 3 + 2 => 2sum(ai) = 55 -20 = 35 odd! so impossible.
Yes, there are only 2 positions for the two 3's to be 3 blocks apart when you're considering 6 blocks numbered 1 2 3 1 2 3.
What about 9 blocks numbered 1 2 3 1 2 3 1 2 3? Then there's only 1 possible arrangement if each 3 is to be 3 blocks apart from another 3, one at each end and one in the middle.
What about 12 blocks, 1 2 3 1 2 3 1 2 3 1 2 3? Then there are none at all as far as I can see.
There is no soluton for nine blocks numbered 1 2 3 1 2 3 1 2 3 ; the middle 3 and the middle 2 would both have to be in the middle (= 5th position) in the sequence, which is not possible.
@@yurenchu Interesting, thanks. I wasn't trying to solve 1 2 3 1 2 3 1 2 3 though, just develop the point Presh was making early on about where to put the 3s (3:43), without considering any of the other numbers for the time being.
It intrigued me that for the 2x123 sequence there are 2 possibilities, which Presh noted. For 3x123 there's only 1, and for 4x123 there don't seem to be any where each 3 block is 3 away from another. It would have to go 3 - - - 3 - - - 3 - - - 3 which is in fact 13 blocks.
@@chrisg3030The 2x1234 sequence has three possible positions for the 4s, the 3x1234 sequence has two possible positions for the 4s, and the 4x1234 sequence has one possible position for the 4s.
In general, the b x {1,2,3,...,n} case involves a sequence with a total length of b*n blocks. Since the "n"-numbered blocks are required to have n blocks between them, they occupy a width of b + (b-1)n = b + (bn - n) = b*n + (b - n) . As long as bn, then the occupied width would exceed the sequence length, hence no solutions for the "n"-numbered blocks is possible.
Computation errors? What computation errors does he mean exactly? Efficient algorithms for dealing with arbitrarily long integer (and also rational) numbers are already available since long time ago.
Another possible method for the 1st question is 2,3,1,2,1,3
It's a cool problem, but in the description of the problem the necessary and sufficient conditions are not well explained. I would say the definitions are subtly but meaningfully incorrect, and also asking for the necessary condition and sufficient condition separately allows for two separate trivially correct conditions that do not imply a necessary and sufficient condition.
At a basic level, necessary and sufficient conditions are the two sides of an if this then that statement. If P then Q, where P is sufficient and Q is necessary. There are other ways to phrase it, but the video’s phrasing is misleading.
For a problem like this, the necessary condition could be in the statement: if this is possible, then n is in this set of values. And for sufficient: if n is in this set of values, then this is possible.
I’ll focus on the necessary condition, but the video’s description of sufficient condition has the same problem. To better match the video’s phrasing, that statement for necessary condition can be turned into the equivalent contrapositive: if n is in this other set of values, then this is impossible.
I think most people would intepret the video's description of the necessary condition as, "What is the set of all values of n for which this is impossible". But that would actually be a necessary and sufficient condition, not just a necessary condition, making the next question about sufficient condition unnecessary.
In order to just be a necessary condition it should be phrased, "What is a set of values of n for which this is impossible?", fixing one issue. Then, one could give the trivial answer n=5 without a more general solution, but that's what it means to be a necessary condition. For arranging the blocks to be possible, it is *necessary* for n not to be 5.
A trivial sufficient condition is that it is sufficient for me to be 3.
To find a necessary and sufficient condition, the problem needs to actually say so. It makes sense to have two separate proofs for the condition being necessary and sufficient in the answer, but it doesn't make sense for the question to ask for the necessary condition and sufficient condition separately.
Seeing the thumbnail I thought it was mortal kombat babality
I managed a solution for both in my head😊
My solution was 231213 and 41312432
Do you want a few palms on the back or something?
I guess the upper limit is [(n-1).(n-2)^(n-1)]/2, total number of solutions has to be less than this,
I have guessed a very similar formula!! But feel it involves factorial too for it to be exact
@@Unidentifying on first try I got a factorial too
It was like. (2n-2)!/2(n-2)!
The number of solutions must be strictly less than (n!)/2 (if we count reverse sequences as a duplicate, like the video does).
A sequence of length 2n is determined by simply taking the left-most of each number (1 through n) and listing them in the order in which they occur in the sequence. For example, the sequence [ *4* *1* *3* 1 *2* 4 3 2] can be referred to as (4, 1, 3, 2). So the number of solutions of length 8 is at most equal to the number of possible permutations of the numbers {1, 2, 3, 4}, which is 4! , and we must then divide by 2 because for every valid sequence there is a valid reverse sequence which is not counted as a separate solution.
And we know it's "strictly less", because the permutation (1, 2, 3,..., n) never corresponds to a valid sequence (because the leftmost block with the highest number n cannot be encountered last).
Since the leftmost block with number n cannot be encountered last of all leftmost blocks, we can even improve this upper bound: there are (n-1)! permutations of numbers {1, 2, 3, ..., n} in which n occurs last. So an improved upper bound for the number of solutions is
(n! - (n-1)!)/2 = (n-1)! * (n-1)/2
Face palm moment for mathematical induction
Can we say that for n=0 there is one (reversible or non reversible) solution?!?
0 mod 4 is 0...
Since in this video they are dividing the proper number of solutions by 2 (because they don't count reverse sequences as separate solutions), I feel that the corresponding "Number of solutions" for n=0 would be 1/2 (instead of 1).
The n's come in pairs. 2 blocks both numbered 0 have 0 blocks between them so would have to be side by side in any solution. So for n=0 there's 1 solution, 0 0. The sequence 0 1 0 1 could have no solution, nor 0 1 2 0 1 2 as far as I can see, but 0 1 2 3 0 1 2 3 could be arranged 3 0 0 2 3 1 2 1.
@@chrisg3030
there wouldn't be any 0 blocks because they start at 1...
buy, mathematically, it "works"...
@@OrenLikes The cases Presh discusses all start at 1, but we don't have to stay with that. Why not start with 2 for example? The blocks 2 3 4 5 6 2 3 4 5 6 could be arranged
4 5 6 2 3 4 2 5 3 6
@@chrisg3030 What @OrenLikes means, is that within the context of Langford sequences as described/defined in the video (in which the lowest-numbered blocks are numbered "1"), for n=0 there would be exactly one valid sequence, namely the so-called _empty sequence_ [] (which is a sequence of zero numbers; or in other words, a sequence with zero length).
Let x(k), y(k) be the positions of the blocks numbered k, where positions are numbered 1,...,2n left to right and y(k) = x(k) + k + 1 in a correct arrangement. Sum up all the positions, we get 2x(1) + 2 + 2x(2) + 3 + ... + 2x(n) + n + 1 = 1 + 2 + ... + 2n. Simplify 4(x(1) + ... + x(n)) = (3n - 1)n. Note the RHS is always even but when is it divisible by 4? Let's try n = 4a + b, 0≤b
In my view, the problem has been completely solved because counting # of solutions for all numbers is a different problem and will never be solved.
...except someone comes up with a generalized version of the solution presented here.
I looked at the number of even and odd numbers.
The set {1,2, ..., 10} has 5 even numbers and 5 odd numbers.
b and b+3 is a pair with one even number and one odd number. The same is true with d and d+5.
That's two even numbers and two odd numbers. We need three more of each.
a and a+2 will either both be even or both be odd. The same is true for {c,c+4} and {e,e+6}. There's no way to get three even numbers and three odd numbers if they are even or odd in pairs.
2 pairs of blocks equals 4 blocks!
Left to right 2, 3, 1, 2, 1, 3
Cooool
*15:57, there’s a typo, “R[S] - reversal…” should be “R[S] = reversal…”. Hope it helps.
6:55 let's number the positions 1-10... 7:06 now if we put a block in Position 'a'...
Ffs...
The question as stated in the thumbnail is incoherent. “… two pairs…”
Fascinating problem! I really enjoyed thinking through this one. A couple of comments:
1. You didn't adequately show that the 4 case only had one solution. You needed to show that the case where the 4's were not on either end did not yield another solution.
2. I thought you were about to claim during your first argument that 1 (mod 4) and 2 (mod 4) were impossible (which was justified) but 0 (mod 4) and 3 (mod 4) were possible. I was thinking to myself no no no just being an integer doesn't guarantee you can distinctly define the values for a_1, ..., a_n. But I didn't think it would be quite so tricky to find them!
3. I see that the p, q, r, s sequences you defined were more or less partitioning 1, 2, ..., 2x-2 and 2x, 2x+1, ..., 4x-3 into evens and odds. The remaining values 2x-1, 4x-2, 4x-1, and (in the 0 (mod 4) case) 4x were placed manually into the sequence. You were doing a proof sketch, but I feel like mentioning what those sets were, like I just did, was meaningful! I think if I'd have written this proof down, I would not have used the variables a, b, c, d and instead named them in terms of x, but that's just my proof style!
My brain hurts after this, lol
Friend is a human being all others are inanimate.
Question 🙋♂️: If I were to place three blocks between the ‘2,2’s…is it not true to state that there are two blocks between them. There is also 1 block between them and two blocks between them. Thus it’s correct to say there are either 1, 2 or 3 blocks between them. My ‘proof’ would be this:
Statement:
A) There are 1, 2 and 3 blocks between them = True
Any number of blocks greater than 3 returns a false statement, as does any number less than 1 block.
B) There are 0 or 4 blocks between them = False
Therefore stating that 1, 2 and 3 or all of these being stated as the blocks between the ‘2,2’s simultaneously is true.
Mathematicians out there…am I correct?
really cool witchcraft
very easy question, why unsolvable?
I got the answer on the first try: 3 1 2 1 3 2. Simple.
A pair is 2. Two pairs of blocks is 4 blocks, not 10.
If you have 2 pairs of blocks then you only have 4 blocks. The rest of the question is moot.
Before I watch your video ..
1 2 3 was easy 2 3 1 2 1 3
1 2 3 4 was harder .. but I did it 4 1 3 1 2 4 3 2
but I'll have to watch your video to see how to PROVE that 1 2 3 4 5 is impossible.
I didn't understand anything 😭
Don't look if you don't want a possible spoiler 312132 or 231213
Six.
2,31213
There you have written impossible question then how do you solve it😂
he didn’t solve, he proved that it’s impossible
312132
41312432
It took me about 35 s to do. Am I doing it wrong?
I solved the first one in 10 seconds
231213