3
votes
0answers
29 views

A question on combinations of a set of numbers

I have the set of the first $n$ primes $\{2,3,5,\ldots,p_n\}$. There are $n^n$ ways of selecting $n$ numbers from this set. Each combination has a number ($C_k$) associated with it and it is the ...
0
votes
2answers
33 views

Ways to add a number using just 1's, 5's, 10's, 25's, 50's

given the set $\{1, 5, 10, 25, 50\}$, in how many ways, can you combine this numbers to get a specific number. For example, 11 can be shaped as $1\cdot11$, or $5\cdot112 + 1\cdot111$, or $10\cdot111 + ...
2
votes
2answers
58 views

Find $\max_{\sigma \in S_n}\sum_{i=1}^n|\sigma(i)-i|$ where $S_n$ is the group of permutations on $n$ letters (Greedy algorithm shows up?)

Find $\max_{\sigma \in S_n}\sum_{i=1}^n|\sigma(i)-i|$, where $S_n$ is the symmetric group of permutations of $n$ symbols. So, the story goes like this: When I first saw the problem, I thought the ...
2
votes
0answers
92 views

Please help me remembering a problem on $n!$ [closed]

I couple of years ago a friend of mine gave me a problem about the digits of $n!$, I never solved it and I also forgot what the question was. It asked you to prove some fact about the digits of $n!$ ...
0
votes
0answers
45 views

Matheletics '13 challenges

I was trying to solve the challenges proposed on Matheletics '13. I'm having trouble solving Hockey Classics, Special Arrangement and Permutation. Can anyone point out the idea I can't see, pls?
0
votes
1answer
47 views

What kind of formula would I use to get all possible outcomes?

I am into a CCG, and I got a question come to mind "how many possible out comes are there for deck combinations?" The game is broken into three: Main Character (6 cards available, only one deck), ...
3
votes
1answer
40 views

How many (linear) order types are there on a set of n elements?

Given number $n$ variables $a_1, a_2, \dots, a_n$. How many way can we place $>$, $=$ between them ? For example, for $n = 3$ (Let's call $a_1 = x, a_2=y, a_3=z$ for convenient). There are 13 way: ...
1
vote
1answer
64 views

English question regarding pigeonhole principle classic question.

Mr. and Mrs. Smith invited four couples to their home. Some guests were friends of Mr. Smith, and some others were friends of Mrs. Smith. When the guests arrived, people who knew each other ...
0
votes
1answer
53 views

Pigeonhole Principle to solve question straightforward

A store wants to celebrate its anniversary and will give a $200 shopping certi cate to the first customer to enter the store whose birthday is the same as that of two other previously admitted ...
1
vote
1answer
149 views

Probability of two dice rolls

If two standard 6 sided dice are tossed what is the probability that a 3 is rolled on at least one of the two? How do I solve this without listing out the possibilities?
2
votes
3answers
187 views

Probability of winning the game 1-2-3-4-5-6-7-8-9-10-J-Q-K

A similar question to mine was answered here on stackexchange: Probability of winning the game "1-2-3" However, I am unable to follow the formulas so perhaps someone could show the ...
14
votes
3answers
298 views

On a Putnam's 2009 problem [duplicate]

Find all even natural numbers $n$ such that the following is true: There is a non-constant function $f : \Bbb{R}^2 \longrightarrow \Bbb{Z}_2$ such that for any regular $n$-gon $A_1...A_n$, $f(A_1) + ...
1
vote
1answer
58 views

What is the relative strength of each of the players in this game?

This is a real life problem. A group of people meet once a week to play a game between two teams. Each round 2 people are randomly appointed captains. Each captain takes turns picking people to be on ...
1
vote
1answer
51 views

Days that cashier will work [duplicate]

A cashier wants to work five days a week, but he wants to have at least one of Saturday and Sunday off. How many ways can he choose the days he will work?
-1
votes
2answers
96 views

Sophomore + Junior + Senior

A class is attended by $n$ sophomores, $n$ juniors and $n$ seniors. In how many ways can these students form $n$ groups of three people each if each group is to contain a sophomore, a junior, and a ...
2
votes
1answer
310 views

Ways to place n non-attacking rooks on an $n^2$ square board.

How many ways are there that we can place n number of non-attacking rooks on an $n \times n$ chess board?
5
votes
2answers
181 views

Combinatorial Proof of ${n\choose{m}}=\frac{n}{m}{{n-1}\choose{m-1}}$

How do prove the following identity combinatorially? $${n\choose{m}}=\frac{n}{m}{{n-1}\choose{m-1}}$$ Any help or hints would be great!
4
votes
1answer
161 views

Board $7\times 7$ problem

An aid in this problem: On a board of $7 \times 7$ each box is painted red or blue so that any square on the board has at least two neighboring boxes blue. determine as little blue boxes that can be ...
1
vote
1answer
74 views

Finding the least number of equations for which that $S-1$ is a component.

Let $S=\sum w$, summed over all words $w=\{x,y\}$ with the same number of $x$'s and $y$'s. Let $\phi$ be the abelianization operator. We know that $$\phi(S)=\sum_{n\geq1}{2n\choose ...
3
votes
1answer
160 views

Partition Proof

Let $\lambda$ be a partition of $N$ of rank $r$. How can I show that: $$\sum_wx^\lambda(w)=f^\lambda(-1)^{t(\lambda)}\prod^r_{i=1}(\lambda_i-1)!(\lambda'_i-1)!$$ where $w$ ranges over all ...
3
votes
2answers
119 views

choosing $5$ non consecutive books from a shelve of $12$

In how many ways can you pick five books from a shelve with twelve books, such that no two books you pick are consecutive? This is a problem that I have encountered in several different forms ...
2
votes
1answer
44 views

Number $e(n)$ of trees with $n+1$ unlabeled vertices $n$ labeled edges

How do I find the number $e(n)$ of trees with $n+1$unlabeled vertices $n$ labeled edges. We're suppose to give a simple bijective proof, I guess? Help appreciated!
1
vote
3answers
95 views

Distinguishable telephone poles being painted

Each of n (distinguishable) telephone poles is painted red, white, blue or yellow. An odd number are painted blue and an even number yellow. In how many ways can this be done? Can some give me a ...
14
votes
2answers
158 views

Simplifying $\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$

How do I simplify: $$\sqrt{\underbrace{11\dots1}_{2n\ 1's}-\underbrace{22\dots2}_{n\ 2's}}$$ Should I use modulos or should I factor them? Or any I suppose to use combinatorics? Any one have a ...
1
vote
1answer
63 views

Power series of $f(x)=\sqrt{\frac{1+x}{1-x}}$

How do I find the power series form of $\,f(x)\,$: $$\displaystyle f(x)=\sqrt{\frac{1+x}{1-x}}$$ I tried to multiply the fraction by $\,\dfrac{1+x}{1+x}\,$ but it didn't help...
3
votes
2answers
751 views

In how many different ways can we place $8$ identical rooks on a chess board so that no two of them attack each other?

In how many different ways can we place $8$ identical rooks on a chess board so that no two of them attack each other? I tried to draw diagrams onto a $8\times8$ square but I'm only getting $16$ ...
20
votes
4answers
320 views

Ways to fill a $n\times n$ square with $1\times 1$ squares and $1\times 2$ rectangles

I came up with this question when I'm actually starring at the wall of my dorm hall. I'm not sure if I'm asking it correctly, but that's what I roughly have: So, how many ways (pattern) that there ...
2
votes
5answers
614 views

Different ordered triples $(a,b,c)$ of non-negative integers

How many different ordered triples $(a,b,c)$ of non-negative integers are there such that $a+b+c=50$? I tried to list the possibilities but the list is way too long, I know how to find the ordered ...
4
votes
1answer
102 views

creating a more complex sudoku (69x6)

I would like to know if its possible to create a "sodoku" with this rule: in a table $69\times 6$ i want to put in the numbers from $1$ to $46$ repeated $9$ times, each numbers HAS to stay in the same ...
3
votes
2answers
62 views

How to solve the non homogeneous equations

I am looking for the proof of the following I have the following equations $x_1^2+x_2^2+x_3^2+....+x_n^2=1$, $x_1+x_2+x_3+........+x_n=1$ $0 \leq x_i\leq 1$ for-all $i$ I believe that the only ...
11
votes
4answers
1k views

Proving identities like $\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}$ combinatorially

I have to give a combinatorial proof of $$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$ I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have ...
5
votes
3answers
104 views

Closed formula for linear binomial identity

I have the following identity: \begin{equation} m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1} \end{equation} I solved for the values and learned of the interpretation of W, X, Y, and ...
2
votes
2answers
409 views

Combinatorial restriction on choosing adjacent objects

I am having trouble understanding an approach to the following problem. Suppose 14 books are aligned in a bookcase. How many ways can we choose 5 books so that no adjacent books are chosen? I think my ...
1
vote
1answer
44 views

Counting Card hands with various restrictions

I would like to know if my solutions are correct for the following three combinatorial card questions. In each question, assume we have a standard deck of cards (13 ranks, and 4 suits). How many ...
11
votes
3answers
497 views

Arc sums for a circle of $k$ positive integers whose total sum is $n$

This problem got me thinking about the following more general scenario: Suppose you have $k$ positive integers with total sum $n$, and you arrange them in a circle. Given such an arrangement, you ...
15
votes
2answers
375 views

Why are braid numbers of the form $Q_h^2$ or $2 \times Q_h^2$?

Consider two piles of $h$ playing cards each, all distinct. Repeatedly take one of the cards on top of one of these two piles and move it on top of one of two new piles, until both of the new piles ...
3
votes
1answer
1k views

Putnam 2012 B3 - Tournament combinatorics

A round-robin tournament among $2n$ teams lasted for $2n-1$ days, as follows. On each day, every team played one game against another team, with one team winning and one team losing in each of the $n$ ...
7
votes
2answers
263 views

Mean and Median in a Classic River Crossing Problem

Consider the following classic problem: Four people on the west side of a river wish to use their single boat to get to the east side of a river. Each boat ride can hold at most two people, and the ...
2
votes
1answer
50 views

Is such a conference possible for $n\ge 1$?

There is a conference with $2n+1$ meetings between $6n+1$ professors. The tables in the conference room are round such that one has $4$ seats and the remaining $n$ tables have $6$ seats each. We know ...
4
votes
4answers
324 views

Mathematical proof for long-term behavior of a sequence of integer vectors

There are some children sitting around a round table. Each child is given an even amount of $1$-cent coins ($0$ is even) by their teacher, all the children at once. A child will give half his money to ...
5
votes
5answers
1k views

Show me some pigeonhole problems [closed]

I'm preparing myself to a combinatorics test. A part of it will concentrate on the pigeonhole principle. Thus, I need some hard to very hard problems in the subject to solve. I would be thankful if ...
11
votes
3answers
371 views

Penguin Brainteaser : 321-avoiding permutations

There are $k$ penguins, $k\ge 3$. They are all different heights. How many ways are there to order the penguins in a line, left to right, so that we cannot find any three that are arranged tallest to ...
0
votes
1answer
75 views

A combinatorics problem refer to this problem?

If i define $f(m,n)=$ $$\sum_{1\leq k\leq mn}\left\{ \frac{k}{m}\right\} \left\{ \frac{k}{n}\right\} .$$ Then prove $$f(m+n,n) - f(m,n) =\frac{n^2-n}{4}$$ for all $m$ and $n$. This question came ...
16
votes
3answers
346 views

A sum of fractional parts.

I am looking to evaluate the sum $$\sum_{1\leq k\leq mn}\left\{ \frac{k}{m}\right\} \left\{ \frac{k}{n}\right\} .$$ Using matlab, and experimenting around, it seems to be $\frac{(m-1)(n-1)}{4}$ when ...
0
votes
1answer
380 views

Equations and Pattern formulas problem solving

I have this question to answer and I need help with finding or creating a equation. You own a license plate manufacturing company. Write a formula or equation that takes a population and ...
2
votes
1answer
113 views

Geometrical combinatorics

This question was inspired by Rush Hour game: You have a 6x6 grid, 12 pieces of size 2, and 4 pieces of size 3. A piece can be placed on the grid either horizontally or vertically. The pieces can't ...
2
votes
1answer
936 views

Permutations and Combinations - How many different ways to do certain things before having to repeat?

Recently, while reading, I came across a problem in Problem Solving Strategies: Crossing the River with Dogs by Ken Johnson and Ted Herr that I was not entirely sure how to solve. Alas, I have come ...
6
votes
1answer
203 views

Vectors inside the unit hypercube.

The following problem has been bothering me for a while, and I finally gave up to solve it on my own. However, I still would like to see a solution: For an arbitrary integer $n$ consider a set of all ...
13
votes
1answer
303 views

How many $N$ of the form $2^n$ are there such that no digit is a power of $2$?

How many $N$ of the form $2^n,\text{ with } n \in \mathbb{N}$ are there such that no digit is a power of $2$? For this one the answer given is the $2^{16}$, but how could we prove that that this ...
2
votes
4answers
6k views

Probability of winning a prize in a raffle

My work is having it's annual Christmas raffle today. 1600 tickets have been sold, and there are 40 prizes to win. I have bought ten tickets. What are the odds I will win a prize? While an initial ...