0
votes
0answers
27 views

An algorithm for linear equation system problem

Is there an algorithm for the following: I have 30 linear Diophantine equations of the following form: $$a_{1,1}x_1+\cdots +a_{1,16}x_{16}=b_1$$ $$a_{2,1}x_1+\cdots +a_{2,16}x_{16}=b_2$$ ...
1
vote
1answer
28 views

Find a polynomial mod $n$ injective on a given set

This question is inspired by this challenge on CodeGolf.SE, in which the goal is to create a hash function with specified collisions. I thought a polynomial over the integers mod $n$ might be a nice ...
4
votes
1answer
59 views

A game problem- double or increment by 1

Its a two player game. Initially $P=1$, and there is some fixed integer $Q>1$. A valid move consists of either increasing $P$ by $1$ or doubling it iff on doing so $P$ does NOT exceed $Q$.The ...
0
votes
1answer
42 views

Degree sequence in $O(n)$

How can we determine the whether a sequence of non negative integers is a valid degree sequence in $O(n)$. I have determined an $O(n\log n)$ algorithm using erdos-gallai theorem.
0
votes
0answers
24 views

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
1
vote
1answer
73 views

Cyclic tower of hanoi problem [duplicate]

If I have 3 rods in a circle and it is allowed to move the disks only in the clockwise direction. How many moves is necessary to move n disks from first rod to the third rod?
8
votes
2answers
113 views

Mathematicly Untangeling Untangle.

I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it. some free games: (but be warned highly addictive) Javascript: ...
1
vote
1answer
34 views

matrix row/col mapping

Many square matrices are symmetric. i.e. $a_{i,j}=a_{j,i}$ For such matrices, we can only store the upper triangle elements, i.e. any $a_{i,j}$ for which $i<=j$. Assume a 10x10 matrix. Using this ...
5
votes
1answer
83 views

Hockey Classics at Matheletics '13

I'm trying to solve a challenge from Matheletics '13: Micheal Nobbs is organizing a training camp for identifying new talents in Indian Hockey. The camp witnessed a total of ($3K+1$) players. Each of ...
2
votes
0answers
65 views

Megaminx parity

I have an old 12-colored Megaminx that I put all new stickers on because the old ones were falling off. This Megaminx was in more of a state of disrepair than I originally thought, though, and when I ...
0
votes
1answer
66 views

number of ways to fill a 2D grid

We have a 2D grid with n rows and m columns, we can fill it with numbers between 1 and k (both inclusive). Only condition is that for each r such that 1<=r<=k ,no two rows must have exactly the ...
0
votes
1answer
147 views

Playing around with ${\int\frac{dx}{x^2-2x}}$

Found the above integral in the old posts and figured I would play around with it using double substitution and integration of partial derivatives. So here goes. $$\int \frac {dx}{x^2-2x}$$ $$= ...
2
votes
2answers
134 views

Rubik's Cube Question

I tried doing a little bit of googling about this, but I am not able to find a decent answer. Let a configuration of a face be a choice of color for each of the 9 squares on that face of the cube. Is ...
7
votes
2answers
225 views

A Nim-like game with conditions and strategies

The game: Given $S = \{ a_1,..., a_n \}$ of positive integers ($n \ge 2$). The game is played by two people. At each of their turns, the player chooses two different non-zero numbers and subtracts ...
6
votes
2answers
193 views

Average complexity of random-pick comparison sort

Motivation. Suppose we have a number of images that we want to arrange in a linear order from the prettiest to the ugliest. At our disposal we have a trained aesthete, whom we can show two pictures ...
1
vote
0answers
47 views

Finding code in 5-guesses only

Suppose you want to crack a code composed of 4 digits (each between 0 to 5 when repetitions allowed) and you get feedback like in mastermind, how can you find it in less than 5 guesses in an ...
2
votes
1answer
68 views

Fair Division: Making the Differences in Players' Valuations Believable

When teaching basic fair division algorithms, the students always propose some simple and (at the first glance) correct solutions for $n$ players, which unfortunately are not correct! The only way I ...
0
votes
1answer
58 views

Non-uniform scaling

I have 10 numbers $x_1, x_2, \dots, x_9, x_{10}$ which sum to a total of $1,000$. I want to scale these numbers so the total is equal to $10,000$, however I don't want them to scale exactly. I'm ...
5
votes
5answers
267 views

pandigital rational approximations to the golden ratio and the base of the natural logarithm

Steven Stadnicki suggested in a comment that I post the following as a question. The golden ration $\phi$ is given by $$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618033988.$$ A rational approximation is ...
5
votes
1answer
190 views

Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed?

Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed? We define $f(n)=m$ where the digits of $m$ and $n$ are reverse. Such as ...
2
votes
1answer
123 views

Checking Sudoku - sufficient sums

Are the following condition sufficient for checking if solution of Sudoku with (extended output) is valide : sum of values in each row, column and subsquare is equal to 45 and sum of squares of ...
2
votes
1answer
622 views

How to calculate $ 1^k+2^k+3^k+\cdots+N^k $ with given values of $N$ and $k$? [duplicate]

Here $ 1<N<10^9$ and $0<k<50$ So we have to calculate it in order of $O(\log N)$.
6
votes
5answers
199 views

How can I find the value of $a^n+b^n$, given the value of $a+b$, $ab$, and $n$?

I have been given the value of $a+b$ , $ab$ and $n$. I've to calculate the value of $a^n+b^n$. How can I do it? I would like to find out a general solution. Because the value of $n$ , $a+b$ and $ab$ ...
2
votes
4answers
288 views

Can you simulate any probability with biased coin throws?

What you're given: $p \in (0,1)$, but you don't know the value of $p$. You have an algorithm $\mathcal{A}_p$ that returns $1$ with a probability of $p$ and $0$ with a probability of $(1-p)$. You ...
1
vote
1answer
252 views

What is the minimum number of moves of solve the puzzle?

There is board in which there are $m\times m$ boxes each assigned an a non zero integer except one box which is marked as $0$ and is treated as vacant. Only the vertical and horizontal neighbors of ...
9
votes
4answers
339 views

A problem about symmetric relations on finite sets.

We have these assumptions: $X$ is a finite set. $\sim$ is an irreflexive symmetric relation on $X$. for any subset $Y\subseteq X$ we define $$\mathcal{Cl}(Y)=\{A\subseteq Y\mid(\forall a,b\in ...
0
votes
1answer
83 views

Compute Birthdate From Age

I have an interesting problem. I want to compute a birthdate (Month Date, Year) from a given age. I understand that subtracting the given age from the current date will supply the year of birth, but ...
3
votes
2answers
264 views

What are good methods for solving Conway's card-stacking puzzle?

Suppose there is a table with three marked spots, $A, B, $ and $C$, on which playing cards can be put, face up. Initially, an ace (1), a deuce (2), and a trey (3) are placed on one or more of these ...
1
vote
1answer
75 views

List number of moves to defeat the opponent

Given the position of chess board of two players, we have to find the minimum number of moves (and output them) so that only one player playing continuously and optimally defeat the other one ...
2
votes
1answer
375 views

What's behind Conway's Game of Life search algorithms?

I've been looking at a program gfind, that searches for spaceships in Conway's Game of Life. The documentation says a bunch of stuff about searching De-Bruijin graphs. I couldn't find any useful ...
3
votes
2answers
467 views

$3 \times 3 $ Magic Square of Squares

On picture below is three-by-three magic square in which seven of the entries are squared integers, found by Andrew Bremner of Arizona State University (and independently by Lee Sallows of the ...
1
vote
1answer
211 views

Cube nets hexomino tilings.

I am looking for an ~12x12 rectangle (small holes and small obtrusions are okay) made entirely of cube net hexominos. It is my understanding that perfect rectangles, in general, are not possible ...
7
votes
2answers
194 views

Density of black cells in rule 110

Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell. Simulation of first 120000 ...
9
votes
3answers
1k views

Secret santa problem

We decided to do secret Santa in our office. And this brought up a whole heap of problems that nobody could think of solutions for - bear with me here.. this is an important problem. We have 4 people ...
3
votes
4answers
617 views

Is there an algorithm to recover a crossword grid based on the clues alone?

Suppose that we have access to only the clues of a crossword puzzle along with the number of letters that the answers are supposed to be. Is there an algorithm that we can use to reconstruct the ...
3
votes
2answers
2k views

How to construct magic squares of even order

Could someone kindly point me to references on constructing magic squares of even order? Does a compact formula/algorithm exist?
19
votes
1answer
419 views

Extracting individual race results from Mario Kart final scores

In Mario Kart, one "cup" involves 4 races, and after every race each racer gets points awarded based on what place they came in (better rank means more points). After playing it enough I grew curious ...
3
votes
1answer
1k views

Mathematical model for solving minesweeper situations

Suppose there's a minesweeper board like the following: 1 1 1 A B C Where A, B, C is an unrevealed square which could contain a mine. This can be represented ...
6
votes
1answer
580 views

How many steps does it take the computer to solve a Sudoku puzzle?

We all know what Sudoku is. Given a Sudoku puzzle, one can use a simple recursive procedure to solve it using a computer. Before describing the algorithm, we make some definitions. A partial solution ...
4
votes
1answer
296 views

Is there any mathematical trick?

Given two natural numbers I am supposed to reverse each of them and then sum them up and reverse the sum to get the final answer. For example if the numbers are $4358$ and $754$ then the answer ...
3
votes
2answers
807 views

Is this version of the Hanoi towers problem NP-complete?

This was really inspired by Solitaire, but a few people reacted with ``oh, it's like the towers of Hanoi, isn't it?'' so I'll try to pose the problem in terms of discs here. Let's start. There are n ...