Combinatorics

Subcategories

• Coinage8 +5

Puzzles

• aba.stringsHow many of the strings of ten characters over the alphabet {a,b} contain the substring aba? New
• abracadabraThe word ABRACADABRA is written as a triangle, one letter per row, the first row holding one A, the second... New
• acyclic.digraphsHow many directed acyclic graphs are there on n labelled nodes? New
• alphabet.blocksWhat is the minimum number of dice painted with one letter on all six sides such that all permutations...
• apply.permutationGiven an array A[0..N-1] and a permutation P of 0..N-1 in another array, rearrange A in place so that... New
• bridge.scheduleGiven N teams, how can they play a round-robin tournament, using N-1 prepared games, so that each team... New
• busPutting 33 students in each bus, the teacher has one student left over.
• chlorinated.dioxinsIn the molecule below, chlorine atoms may be attached to any of the 8 outer carbon atoms. New
• colorAn urn contains n balls of different colors.
• counters.beyond.diagonalHow many ways are there to place n counters, diagonal by diagonal, starting from a single counter, so that... New
• covering.recordsTable A lists all 70 combinations of the 8 letters A-H taken 4 at a time; table B lists all 28 combinations taken 6 at a time. New, unsolved
• cube.colouringHow many distinguishable ways are there to paint the faces of a cube using two colours, counting patterns... New
• directed.animalsHow many sets of n squares in the quarter plane contain the corner square and can each be reached from the... New
• disks.on.pegsTwelve disks, each with holes at some of six positions, are to be rotated and stacked so that the pegs pass through them. New
• doors.and.buttonsThere are n doors, and n buttons that control them. New
• euler.circuitsFind a closed formula for the number of Euler circuits on a complete (undirected) graph of n nodes. New
• finite.groupsHow many groups are there of each order up to 16, and what are their multiplication tables? New
• five.sleepersFive people stay overnight in a hotel. New
• fullConsider a string that contains all substrings of length n.
• golf.foursomesSixteen golfers play in foursomes on six different days. New
• golomb.rulerBetween Kroflite and Beeline are five other towns. New
• gossipn people each know a different piece of gossip.
• grid.countingIn an n x n grid of squares, how many squares are there? New
• grid.dissectionHow many (possibly overlapping) squares are in an mxn grid?
• grid.tourA city has 36 locations on a 6x6 grid of roads. New
• happy.cube.pieces"Happy Cube" puzzles each have six square pieces, to be assembled into a hollow cube. New
• josephusYou are one of 1000 captured pirates about to be tied to posts numbered 1 to 1000 arranged in a circle. New
• langfordCan the pattern of 312132 and 23421314 be continued: numbers made of pairs of each digit 1..n, with the two... New, unsolved
• lights.in.circleWe place n lights L_0, L_1, ..., L_{n-1} on a circle. New
• lucky.ticketHow many six-digit tickets (000001 to 999999) have the sum of the first three digits equal to the sum of... New
• multipermutationsIn how many ways can 3n elements be chosen out of an n*n array with exactly 3 in each row and column? New
• no.consecutive.neighborsPut the numbers 1 through 8 into the boxes of this diagram so that no two consecutive numbers are in boxes... New
• np.completeWhat does it mean that a problem is "NP-complete"? New
• odd.permutation.productLet A1, A2, ..., An be any permutation of the numbers 1, 2, ..., n. New
• paths.through.gridHow many distict paths exist from one corner of a rectangular grid to the opposite corner, traveling along...
• permutationCompute the nth permutation of k numbers (or objects).
• phone.dialingHow many telephone numbers can be dialed if each digit is reached from the previous one by a move of a... New
• pizza.toppingsA pizza deal: for one low price you get two pizzas, each with up to 5 toppings chosen from 11. New
• plutarch.numbersPlutarch reports that Hipparchus counted 103,049 compound propositions "on the affirmative side" and... New
• raised.buttonsA 3 x 3 grid of buttons, numbered like a keypad New
• roller.coasterFour people line up for a roller coaster. New
• round.robinSchedule a round robin tournament in which there are N teams, each one playing all the others, in the... New
• same.handshakesProve that if n people attend a party, there will be at least two people who shake the same number of hands. New
• shannon.switching.gameIs there an algorithm for determining whether a given undirected graph has two edge-disjoint spanning trees... New
• shuffling.machineA device which shuffles cards always rearranges them in the same way relative to the order in which they were placed into it. New
• sliding.pairsTake three white poker chips and three red poker chips, line them up thusly: New
• sorting.boundsSorting n keys by binary comparisons needs O(n log n) steps on average; can a sort be faster than O(n log... New
• squarefree.stringsWhat is the longest repetition-free string one can build with {0,1,2}? New
• stamp.foldingIn how many ways can a strip of n blank stamps be folded? New
• subsetsOut of the set of integers 1,...,100 you are given ten different integers.
• sum.distinct.setsConsider an ordered set of n integers, {M(n,i), i=1 to n}. New
• sum.free.groupsArrange the numbers 1...23 into three groups so that in any group the sum of two numbers from that group is not in that group. New
• target.practiceA marksman shoots n cans off a fence, the first anywhere and each later one next to a gap; in how many... New
• teaching.scheduleA teacher at a school with grades 1 through k wants a schedule, repeated every k years, in which she... New
• tictactoe.arrangementsHow many ways are there of arranging 3 crosses and 3 noughts on a 3x3 tictactoe board (excluding rotations... New
• transitionsHow many n-bit binary strings (0/1) have exactly k transitions (an adjacent pair of dissimilar bits, i.e.,...
• true.false.quizHow many answer sheets must you submit to a 10-question true/false quiz to be sure one of them scores at... New
• vassiliev.conjectureIs a certain linear map between two vector spaces of graphs with univalent and oriented trivalent vertices one-to-one? New, unsolved