text:
Impartial games with entailing moves

Combinatorial Game Theory has also been called `additive game theory', whenever the analysis involves sums of independent game components. Such disjunctive sums invoke comparison between games, which allows abstract values to be assigned to them. However, there are rulesets with entailing moves that break the alternating play axiom and/or restrict the other player's options within the disjunctive sum components. These situations are exemplified in the literature by a ruleset such as nimstring, a normal play variation of the classical children's game dots & boxes, and top entails, an elegant ruleset introduced in the classical work Winning Ways, by Berlekamp Conway and Guy. Such rulesets fall outside the scope of the established normal play theory. Here, we axiomatize normal play via two new terminating games, ∞ (Left wins) and ∞ (Right wins), and a more general theory is achieved. We define affine impartial, which extends classical impartial games, and we analyze their algebra by extending the established Sprague-Grundy theory, with an accompanying minimum excluded rule. Solutions of nimstring and top entails are given to illustrate the theory.

• 11 publications
• 4 publications
• 1 publication
07/23/2022

Constructive comparison in bidding combinatorial games

A class of discrete Bidding Combinatorial Games that generalize alternat...
07/12/2022

Sprague-Grundy values and complexity for LCTR

Given a Young diagram on n boxes as a non-increasing sequence of integer...
07/17/2022

Bidding combinatorial games

Combinatorial Game Theory is a branch of mathematics and theoretical com...
03/11/2021

A Reinforcement Learning Based Approach to Play Calling in Football

With the vast amount of data collected on football and the growth of com...
09/28/1998

Evolution of Neural Networks to Play the Game of Dots-and-Boxes

Dots-and-Boxes is a child's game which remains analytically unsolved. We...
04/19/2018

Making Change in 2048

The 2048 game involves tiles labeled with powers of two that can be merg...
07/20/2017

Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs

Pebble games are single-player games on DAGs involving placing and movin...

1 Introduction

Combinatorial Game Theory (CGT), as described in [1, 3, 5, 8], considers disjunctive sums of normal play games. In order to evaluate the outcome of a sum of such games, it suffices to analyze the components individually, and then add the individual values.

However, some classical impartial rulesets, such as nimstring and top entails fall slightly outside the usual CGT axioms. In nimstring, certain moves require a player to play again, or carry-on, which is a violation of the alternating play axiom. And in top entails, certain moves enforce the next player to play in the same component, which violates the standard definition of a disjunctive sum. Thus, values of individual components is no longer a relevant measure, given the standard CGT axioms. The type of moves mentioned in this paragraph will be gathered under the term entailing moves.444Entailing means “involve something as a necessary or inevitable part or consequence”.

The purpose of this paper is to extend impartial normal play games sufficiently to include games with entailing moves. While accomplishing this, we expand the classical Sprague-Grundy theory to fit this extension.

We will rebuild the normal play axioms by using so-called terminating games, or infinities, and . Here we focus on the impartial setting, and the general comprehensive theory for partizan games will appear in [6].555There are partizan rulesets, in the literature and in recreational play, with similar entailing and terminating

moves. Probably the most prominent ones are the game of

chess, and a version of go called atari go. These theories are called affine impartial and affine normal play respectively.

Although we consider only impartial games in this paper, we will keep the players distinguished as Left and Right. In particular, Left wins if either player plays to , in any component, and Right wins in case of play to . Note that the normal play zero is restored by defining , a first player losing position.

It is well-known that, in classical Combinatorial Game Theory, the impartial values are nimbers. We will prove that there is exactly one more value modulo affine impartial, a game , called the moon. This value was anticipated in the classical work Winning Ways, by Berlekamp, Conway and Guy. In [3], volume 2, page 398, one can read “A loony move is one that loses for a player, no matter what other components are.”. Before developing the theory, we illustrate how the infinities are used in the motivating rulesets, nimstring ([2, 3]) and top entails ([3], volume 2).

Let us first briefly mention the organization of the paper. To facilitate the development of the new impartial theory, Section 2 considers the basic properties of unrestricted affine normal play, aiming for a game comparison result, Theorem 14.The affine impartial theory is developed in Section 3. The main result is Theorem 34 which shows that values in this extension are the nimbers plus one more value. Theorem 39 gives an algorithm to find the value of a given position, and notably, if there are no infinities in the options, then the nimbers are obtained by the usual mex-rule. We finish off with two case studies. In Section 4, we compute the value of an interesting nimstring position, anticipated in Section 1.1. In Section 5, we compute the values for top entail heaps of sizes through , and Theorem 41 provides theoretical justification for computing top entails values.

1.1 The ruleset nimstring

In nimstring, a player draws a line between two horizontally or vertically adjacent points, in a finite grid, not already joined by a line. If a player completes a square, then they must draw another line, and if they cannot do so, they lose.

Figure 1 shows an example position, where no square can be completed in the next move. Later, through the new theory, we will see that the position equals modulo affine impartial.

In Figure 2, we show a position, , with two options, one of which is an entailing move. Namely, if the the top bar is drawn, the next player continues, but if the middle bar is drawn, then the current player has to carry-on.

When we develop the theory, we will see that the position , to the left in Figure 2, is the abstract game

 {{∞∣0},0∣{0∣¯¯¯¯¯¯∞},0}. (1)

The option 0 is obtained by drawing the top bar. The intuition for this is as follows: the player who moves inside the ‘double box’ loses, if is played in isolation, because they have to play again.

If a player draws the middle bar in , then they have to carry-on, and this is represented by the abstract option , if Left moved. There is an infinite urgency in this game: Right has to play here, or lose. And so, the effect is the desired: Left plays again, and alternating play is restored. Hence disjunctive sum play is also restored, within the affine impartial convention. Moreover, the Right option in this threat should be 0, because Left loses by playing this option if is played alone. If the sum is , with as in Figure 1, then the next player wins, by playing this entailing middle bar in .

1.2 The ruleset top entails

Top entails is played on heaps of tokens. A player may either remove the top token from exactly one heap, or split a heap into two non-empty heaps. If the top token is removed from a heap, then the next move (in alternating play) must be played on the same heap.

A heap with one token, say , is a first player win, in any situation. Namely, a move in forces the opponent to play in the same heap, where no move remains. Note that the abstract game settles this behaviour. The player who moves first in wins independently of existence of other components. The point we wish to make here is that this abstract representation settles the problem of independecny of a heap of size one with other disjunctive sum components.

Consider , in Figure 3, a pile of size 3. There are two options, as depicted in Figures 4 and 5.

The option in Figure 4 splits into two piles and the next player’s options are unrestricted. By the terminating effect of playing in a heap of size one, this composite game should be equal to the game .

The option in Figure 5 is an entailing move, and the next player must continue in this component, even if other moves are available. Therefore, the game form of the entailing option in Figure 5 is

 {∞∣1+1,1entail},

if Left just moved, and where 1 denotes a heap of size one. The terminating threat forces Right to play here, instead of possibly using other options.

Intuitively, either way of responding reduces to a game of the form . In conclusion, the heap of size three should be equal to the game , and disjunctive sum play has been restored. All this intuition will be rigorously justified in the coming complete theory for affine impartial play.

It turns out that affine impartial games require only a small extension to the Sprague-Grundy theory. Namely, the game in (1), obtained from the nimstring position in Figure 2, equals the game in the previous paragraph, modulo affine impartial, and later we will devote the value ‘ ’ to the equivalence class of such games.

2 Affine literal forms and order

This section aims at Theorem 13, a comparison theorem for affine normal play that suffices for the purpose of this paper. We begin by defining the fundamental concepts for affine normal play, and we wait with the restriction to affine impartial until the next section.

In classical Combinatorial Game Theory, the normal play forms, , are recursively constructed from the empty set. The form is the only form of day zero and the only form without options. The forms , , , are born on day 1, and so on.

The forms of affine normal play, denoted , are recursively constructed from the games (infinity) and (minus infinity) [6]. The forms and are the only forms without options. The forms and are born on day zero. And so on.

The order of is defined in the standard way. Consider the four perfect play outcome classes (Left wins), (Next player wins), (Previous player wins), and (Right wins). From Left’s perspective, the first outcome is the best (she wins, regardless of playing first or second) and the fourth is the worst (she loses, regardless of whether playing first or second). On the other hand, regarding and , the victory depends on playing first or second, so these outcomes are not comparable. These considerations explain the partial order in an ‘outcome diamond’:

We write , or equivalently , if the outcome of is Left wins, and so on. The evaluation of games in is based on the following axiomatic list:

Axiom 1 (Absorbing Nature of Infinities).

The infinities satisfy

1. ;

2. ;

3. For all , ;

4. For all , ;

5. ’ is not defined.

Addition of games is defined as usual, apart from items 3 and 4. The fifth item is natural in terms of perfect play, since if  appears, then  cannot appear and vice versa.

The definitions of equality and partial order of games are based on the outcome diamond.

Definition 2 (Order and Equality of Games).

Let . Then, if, for every form , . Moreover if and .

Note that the exclusion of the infinities does not diminish the generality of the definition, but is necessary due to Axiom 5. As usual, we have the following observations. If then replacing by or by do not hurt the players under any circumstances. Similarly, if then replacing by does not hurt Left, and replacing by does not hurt Right.

Let . Then and .

Proof.

If then, by Axiom 3, . Hence, by Axiom 1, . Therefore, for every , we have , and so . Proving that is analogous. ∎

The concept of a check is fundamental to . Indeed, this is an alternative, and perhaps more explicit, at least for those Chess playing readers, term for an entailing move, as seen in the Introduction.

Definition 4 (Check Games).

Consider . If () then is a Left-check (Right-check). If is a Left-check or a Right-check then is a check. Denote by () a Left (Right) option of that is a Left-check (Right-check).

Of course, all checks are asymmetric, apart from the ‘trivial check’, . A player would not use this check, because the opponent ‘check mates’ by defending.

Definition 5 (Quiet Games).

Let . If () and is not a Left-check (Right-check) then is Left-quiet (Right-quiet). If is Left-quiet and Right-quiet then is quiet.

Definition 6 (Conway Forms and Games).

A game is a Conway form if , and has no checks as followers. Let denote the substructure of Conway forms. A game is a Conway game if it equals a Conway form.

Example 7.

The game is a Conway form (no checks as followers). The game is not a Conway form because there are checks as followers. However, later, we will see that . Therefore, is a Conway game.

In general, when we say form, we mean the literal form, and when we say game, we usually mean (any member in) the full equivalence class of games. When we write , we usually refer to the literal form, but the context may decide.

Some classical theorems are still available in .

Theorem 8 (Fundamental Theorem of Affine Normal Play).

If then if and only if .

Proof.

Assume that . We have , and so, by order of outcomes, .

Suppose now that . If , by Theorem 3, ; hence, assume . Let .

If, playing first, Left wins with the option , then she also wins with the option . Essentially, she mimics the strategy used when is played alone, answering locally when Right plays in . Due to the assumption , this is a winning strategy for Left in .

If Left, playing second, wins . Then, on , she can respond to each of Right’s moves locally, with a winning move on the same component, because . Thus Left can win playing second.

Therefore, and so, . ∎

Corollary 9 (Order-Outcome Bijection).

If then

• if and only if ;

• if and only if ;

• if and only if ;

• if and only if .

Proof.

The statement of Theorem 8 can equivalently be “ if and only if ”, so we can use that fact too.

Suppose that . By Theorem 8, . But, we cannot have , for otherwise and . Therefore, . Conversely, suppose that . By Theorem 8, we have . But, we cannot have , for otherwise , and . Hence, . Thus, the first equivalence holds.

The proof of the fourth equivalence is analogous.

For the second equivalence, if , then . So, .

The third equivalence is a consequence of eliminating all other possibilities. ∎

It is known that is a group. By Corollary 9 we may deduce that is only a monoid. Namely, if then, for any , (playing first, Left wins). Hence, for all , and is non-invertible. Thus, in general, the comparison of with cannot be done by playing the game ‘’, because, sometimes, ‘’ does not exist.

However, the following theorem shows that not everything is lost.

The conjugate of a given game switches roles of the players.

Definition 10 (Conjugate).

The conjugate of is

 \vboxto0.0pt\ex@\curvearrowleftright\vssG=⎧⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪⎩¯¯¯¯¯¯∞,if G=∞∞,if G=¯¯¯¯¯¯∞{\vboxto0.0pt\ex@\curvearrowleftright\vssGR∣\vboxto0.0pt\ex@\curvearrowleftright\vssGL},otherwise,

where denotes the set of literal forms , for , and similarly for .

Theorem 11.

If is a Conway game, then is invertible and .

Proof.

Suppose first that is a Conway form. If then , and thetheorem holds. Otherwise, let us verify that is a -position. If Left, playing first, chooses , because this game is not ( is not a check), Right can answer with and, by induction, because is a Conway form with no checks as followers, that option is equal to zero. Because of that, by Corollary 9, that option is a -position, and Right wins. Analogous arguments work for the other options of the first player, and so, is a -position. Again, by Corollary 9, .

Suppose now that is not a Conway form. Because it is a Conway game, by definition, it is equal to some . The first paragraph proved that . Also, by symmetry, is equal to . Therefore, implies . ∎

Lemma 12.

Let , and let be an invertible form of . Then

 G≽H⇔G+J≽H+J.
Proof.

() Consider any and let . Since is invertible, is neither nor , and so, is neither nor . Definition of order implies , that is . Thus, the arbitrariness of implies .

() Consider any and let ( is invertible, i.e. exists and ). Since is invertible, is neither nor , and so, is neither nor . By definition of order, , that is . Hence, , and so, given the arbitrariness of , . ∎

Theorem 13.

Let be any form of and suppose that is an invertible form of . Then,

 G≽H⇔G−H∈L∪P and G=H⇔G−H∈P.
Proof.

By Lemma 12, . Therefore, we have . By Theorem 8, this is the same as .

Finally, , by . ∎

Theorem 14.

Let be any form of and let be a Conway game. Then

• if and only if

• if and only if .

Proof.

These are direct consequences of Theorems 11 and 13. ∎

In a follow up paper [6], where we study the full game space , we provide a solution of the general case of .

3 Affine impartial theory

In order to propose an extension of the Sprague-Grundy theory, we first define the concept of an affine impartial game.666In terms of ruleset: here ‘affine impartial’ is an abbreviation of affine normal play impartial, in the sense that if the player to move cannot complete their move they lose. Of course, rulesets like nimstring should be impartial.

Definition 15 (Symmetric Game).

Consider a form . Then is symmetric if and .

Definition 16 (Affine Impartial).

A form is affine impartial if it is symmetric and all quiet followers of are symmetric. The subset of affine impartial games is .

Of course, a non-quiet game either has no option, or is a check, and so (unless a trivial check) is by definition asymmetric. But this is the only exception of symmetry in the world of affine impartial impartial games. It is easy to check that satisfies the standard closure properties of combinatorial games, i.e. closure of taking options, addition, and conjugates.

The following result must hold for any class of games that claims to be “impartial”.

Theorem 17 (Affine Impartial Outcomes).

If is a symmetric form, then .

Proof.

This proof uses a strategy-stealing argument. Suppose that . Then Left wins playing first with some option . Hence, by symmetry, Right wins playing first with . That contradicts . A similar argument holds against . ∎

We want to restrict our analysis to . Therefore, we define equality modulo .

Definition 18 (Impartial Equality).

Consider forms . Then, if, for every form , .

Observation 19.

Of course, in implies . The opposite direction is not true. We can have and in , if the there is no distinguishing game in . A simple example is and . As we will see, these games are indistinguishable modulo . However, the game distinguishes them in ; playing first, Left wins , but loses .

It is easy to verify if a form in equals a nimber.

Theorem 20 (Nimbers).

Let . Then, if and only if .

Proof.

Suppose that . By Theorem 14, modulo , and so .

Suppose now that . By Theorem 17, , since impartiality is closed under addition. If , then and , contradicting . Hence, . ∎

Notation 21.

Let denote the subset of affine impartial games that equal nimbers.

It is well-known that, in classical Combinatorial Game Theory, the impartial values are nimbers. We will prove that there is exactly one more value modulo , a game , called moon. In [3], volume 2, page 398, one can read “A loony move is one that loses for a player, no matter what other components are.”. The following general definition is motivated by that idea.

Definition 22 (Loony Game).

A game is loony if, for all quiet , .

Thus, in our interpretation, a ‘loony move’ exposes a loony game.

There are no loony games in . Suppose that is a loony game. Of course, and that is a contradiction. Suppose that is a loony game. In that case, if is large enough, , and that is a contradiction, since is quiet.

There are loony games in . The obvious one is , but we can also have impartial quiet loony moves. Consider and a quiet such that . If , the first player wins moving to . If , the first player wins moving to (Left) or to (Right).

Notation 23.

The moon is the game form .

When a player moves to , for any , he “goes to the moon” and loses.

Theorem 24 (Loony Uniqueness).

All loony games are equal modulo .

Proof.

Consider and , two loony games. We know that all quiet belong to . By definition of a loony game, we have and . On the other hand, if is not quiet then and , and hence and . In all cases, and the theorem holds. ∎

Observation 25.

Two loony games may be different modulo , but equal modulo . The games and are loony. These games are different modulo . Left, playing first, loses and wins . However, as will follow by theory developed here, one cannot distinguish these two games modulo .

In order to prove an affine impartial minimum excluded rule, we separate the options into two classes.

Definition 26 (Immediate Nimbers).

Let . The set of -immediate nimbers, denoted is the set .

Not that, by symmetry, , and note that .

Definition 27 (Protected Nimbers).

Conisder a game form . The set of -protected nimbers is

1. , if ;

2. , otherwise.

The second item says: if then if there is a check such that Right, playing first, loses . That is, playing first, Left is protected against those nimbers in a disjunctive sum.

Similar to Definition 26, we could have defined with respect to Right options, to obtain the same set.

Note that . This statement holds for the literal form . However, one can show that by using instead the form , as in (1), then . The output of “protected” is sensitive to which form we choose.

When the underlying game form is understood, we simply refer to the immediate and protected nimbers, respectively.

Example 28.

Let be such that the Left options are , , and . Of course, . On the other hand, playing first, Left can use the check to win . Because of that, . An important observation is that, although Left is protected against the nimber , Left cannot force a Left move to in . But if Right moves to 0, Left wins anyway

Sometimes, Right can manoeuvre Left’s eventual play to a nimber, or worse, via a sequence of ‘check upon check’.

Definition 29 (Manoeuvrable Form).

A quiet form is manoeuvrable if after each Left move that is neither a nimber nor , Right can force, with checks, a Left move to a nimber or a move by either player to .

Example 30.

The form is manoeuvrable. If Left avoids the immediate nimber , by checking, then Right can still force Left to move to one of the nimbers or .

Lemma 31.

If is manoeuvrable, then is finite.

Proof.

After a Left first move in , if needed, Right can force with checks a Left move to a nimber or a move by either player to . Let be the set of nimbers that can arise through this forcing strategy by Right. Then is finite, because we study short games. Let be a nimber such that, for all , we have . In , after a first check, say, to , Right forces with checks a move by either player to or a Left move to (). In the second case, after the sequence, Right wins with a TweedleDee-TweedleDum move. Thus, Left can protect against at most a finite number of nimbers. That explains why is finite in case of manoeuvrable games. ∎

Let denote the smallest nonnegative integer not in . Let denote the set of Sprague-Grundy values of a set of nimbers, i.e. if , then .

Lemma 32.

If is manoeuvrable then equals the nimber , where .

Proof.

By Lemma 31, we know that is finite. Let . Let us argue that the game . If the first player moves in to a nimber , because is excluded from , he loses. If the first player moves in to a quiet not nimber , because is not a nimber, (Theorem 20), and the first player also loses. If the first player moves in , giving a check, because is excluded from , he also loses. Finally, if the first player moves to (), because is the minimum excluded from , he loses because the opponent has a direct TweedleDee-TweedleDum move or wins with a check. Hence, by Theorem 20, . ∎

Lemma 33.

If are not nimbers, then .

Proof.

Consider . For a contradiction, assume that the sum of the birthdays, , is the smallest possible such that . Note that, by the assumptions on and , . Without loss of generality, we will analyze the move from to . First, we prove two claims that concern local play in and respectively.

Claim 1. Playing second in , Left can avoid Left moves to nimbers and moves by either player to until the first Right-quiet move.

Proof of Claim 1. Suppose that Right, playing first in , could force a Left move to a nimber or a move by either player to . If so, in , by giving checks in , Right could force some (Right’s turn) or a move by either player to

. Of course, the second situation would be a victory for Right. Regarding the first case, at that moment, the position would be

. And, because is not a nimber, by Theorem 20, we would have , which is a winning move for Right. In either case, Right, as first player, would win. That would contradict .

Claim 2. There is an such that Left can avoid Left moves to nimbers and moves by either player to , until the first Right-quiet move.

Proof of Claim 2. This is exactly the same as saying that is non-manoeuvrable. If it was manoeuvrable, by Lemma 32, it would be a nimber, and we would have a contradiction again.

Let us return to the move from to . Because , Right has a winning move from . But, by Claims 1 and 2, Left can play such that, at any stage before a Right-quiet move, Right is moving on , where is a follower of and is a follower of , such that neither nor is a nimber.

Either way, by assumption, there is a winning quiet Right-move or . Since these are impartial games, we must have or . But, because and are not nimbers, it follows by Theorem 20 that and are not nimbers.

Therefore, we have or with both components not nimbers. But this contradicts the smallest birthday assumption. The result follows. ∎

Theorem 34 (Affine Impartial Values).

Every affine impartial form equals a nimber or the game .

Proof.

Let . If there is some such that , then , by Theorem 20.

Suppose next that , for all , so that does not equal a nimber modulo . By Lemma 33, for all , we also have . Hence, for all , we have , and therefore is a loony game. Because, by Theorem 24, all loony games are equal modulo , and is a loony game, we have . ∎

Observation 35.

A form can be loony modulo and not loony modulo . An example is the form . This game is not loony modulo because, if , playing first, Left loses . However, . This follows, by Theorem 34, since does not equal any nimber; if Right starts , he wins, by an appropriate parity consideration.

Theorem 36.

The game is absorbing modulo , that is, , for all .

Proof.

Since , regardless of what is, the first player wins both and . Therefore, by definition of equality of games, . ∎

Corollary 37.

The game is an idempotent modulo , that is, .

Proof.

This is a trivial consequence of Theorem 36. ∎

Definition 38.

The Sprague-Grundy value of the moon is .

The following theorem explains how the Sparague-Grundy value of is determined by the set .

Theorem 39 (Affine Impartial Minimum Excluded Rule).

Let . We have the following possibilities:

• If , then and ;

• If , then .

Proof.

If , we have for all . Because of that, is not a nimber and, by Theorem 34, . If , we use the same argument of the proof of Lemma  32. ∎

Corollary 40.

If all the options of a game are quiet then is a nimber.

Proof.

If all the options of a game are quiet, then . Therefore, and, by Theorem 39, . ∎

4 Case study: nimstring

In the introduction, we promised to show that the following component equals .

Study the positions:

All (a), (b), (c), (d), and (e) are -positions. The game value of (f) is .

Other positions that equal  are the following.

In the position (l), the central horizontal move is the option (d), that is equal to . The other options are (f) and (g), that are equal to . Therefore, the literal form is

 l={0,\scalebox1.1$$,\scalebox1.1$$∣0,\scalebox1.1$$,\scalebox1.1$$}

with , and . Applying the affine impartial minimum excluded rule, we conclude that the position is .

The position (m) is also equal to , i.e. .

Now, we are ready for (n), a more complex situation. The literal form is

 n={h,i,k,{∞|l}|h,i,k,{l|¯¯¯¯¯¯∞}},

that is,

 n={,,,{∞|∗}|,,,{∗|¯¯¯¯¯¯∞}}.

Hence, , and . Applying the affine impartial minimum excluded rule, we conclude that the position is .

Going back to the original question, we have the following.

The form is , that is, . Here n represents a play of the top or bottom bar, m represents a play of some middle bar, and c represents play of the left line.

5 Case study: top entails

We denote by the literal form of a stack of size . The literal form of the Left removal of the top coin from a stack of size is (and the symmetric from Right’s point of view). With that in mind, let us compute the first few values. First, we do it the tedious way, and then later after Theorem 41, we propose the slick recursive way for a few more values, in a table format.

Of course, . The first player loses. Moreover,

• . Therefore, and . Using the affine impartial minimum excluded rule, . In the next step, for ease, we will use the form .

• . Therefore, and . Using the affine impartial minimum excluded rule, .

• . This game is equal to . Therefore, and . Using the affine impartial minimum excluded rule, . In the next step, for ease, we will use the form .

• . This game is equal to. Therefore, and . Using the affine impartial minimum excluded rule, .

• . This game is equal to . Therefore, and . Using the affine impartial minimum excluded rule, .

• . This game is equal to . Therefore, and . Using the affine impartial minimum excluded rule, .


text:
Next.js is great to give our React apps a big set of built-in features that are essential in Web applications.

It gives us just a little bit of structure for our project files.

All visible pages stay under the /pages folder. API routes stay under the /pages/api folder. Publicly visible files under /public.

That’s basically all. The rest is all on us.

What I commonly do is this.

All the React components required by pages are in a /components folder.

I usually have a /components/Common folder, and then I re-create the pages structure:

• /components/Common
• /components/Home
• /components/Profile

… and so on.

Then I have a lib folder that contains all the utilities used by the React components or the API routes. It might be data fetching, a library initialization, the Prisma setup, database access, a fetcher for SWR, the easy-peasy store.. basically anything that could be reused anywhere but it’s not a component.

I also make sure that I can include them like this:

import comp from components/Common/comp
import x from lib/x

using this little setup in jsconfig.json:

{
"compilerOptions": {
"baseUrl": "."
}
}

I mentioned Prisma, which I use frequently. That’d need its own /prisma folder for the schema and the migrations, and maybe an SQLite database if needed.

If the site has content, in form of markdown for example, I’ll add a /content folder.

For middleware (sometimes it’s useful), /middleware but it’s quite rare.

This will work fine for almost all the things you’ll need.

## One more thing! ⚠ ✋

At the end of January I will organize the Web Development Bootcamp.

It's a 10-weeks long cohort online course where I will guide you to becoming a Web Developer.

It's not "just a course". It's a big event I organize once a year.

We'll start from zero, learn the fundamentals of Web Development, HTML CSS, JavaScript, Tailwind, Git, using the command line, VS Code, GitHub, Node.js, we'll then learn React, JSX, how to use PostgreSQL, Astro, Next.js, Prisma, deploying on Netlify/DigitalOcean/Fly/Vercel and much more!

At the end of the first 10 weeks you'll know how to create web sites and web applications and I'll unlock you the 2nd phase of the Bootcamp: you will get access to a large number of projects exclusive to the Bootcamp graduates, so you can follow my instructions to build things like private areas with authentication, clones of popular sites like Twitter YouTube Reddit, create e-commerce sites, and much much more.

Because once you got the fundamentals, you only learn by working on real, exciting projects.

To find out more, visit bootcamp.dev

format: plain


text:
# Collisional models

1. Jul 8, 2011

### carltropper

I would like find references to collisional astrophysics models. I am a computer scientist interested in developing discrete event n body algorithms and would like any help that I can get. I have developed a direct n body algorithm for systems without collisions which seems to work well and would like to find out if it makes sense to try my hand at the world of collisions.

2. Jul 8, 2011

### zhermes

What type of collisions are you hoping to do?
Generally, even in few-body simulations, collisions are dealt with using some (incredibly) simple prescription, e.g. the "sticky star" approximation in which stars simply merge, and conservation of mass, momentum, and energy is enforced. In stellar evolution models, systems which collide are often just removed from the simulation.

Full collisions are generally only done in full hydrodynamics calculations.

You might want to take a look at Gadget (an industry standard).

3. Jul 8, 2011

### carltropper

Thank you very much for your reply. I guess this means that collisional models are not really worthwhile expending much energy on as they are simple extensions of collision type models.


text:
# How many unit cylinders can touch a unit ball?

What is the maximum number $k$ of unit-radius cylinders with mutually disjoint interiors that can touch a unit ball?

By a cylinder I mean a set congruent to the Cartesian product of a line and a circular disk. The illustrations, copied from 2, show various configurations of six cylinders, perhaps all possible - up to isometry. The question is about 25 years old; the answer is conjectured to be 6, but the conjecture is still unconfirmed. Heppes and Szabó 1 proved in 1991 that $k\le 8$; nine years later Brass and Wenk 2 improved this result to $k\le 7$. Also, one would like to know:

What does the configuration space of six unit cylinders touching a unit ball look like?

In particular,

Is the configuration space connected?

Even more specifically, referring to the configurations shown below:

Within the configuration space, is a continuous transition possible from the configuration in Figures 1 and 2 to the configuration in Figure 3?

The last question may be possible to verify by a natural candidate, but the necessary computations seem too tedious to me...

1. Heppes, Aladar and Szabó, Laszló. "On the number of cylinders touching a ball." Geom. Dedicata 40 (1991), no. 1, 111–116; MR1130481.

2. Brass, Peter and Wenk, Carola. "On the number of cylinders touching a ball." Geom. Dedicata 81 (2000), no. 1-3, 281–284; MR1772209.

-
(This is a useless tangent, but the rightmost image in Fig.3 occurred in another MO question asking a different question: Blocking visibility with cylinders.) – Joseph O'Rourke Jan 28 '14 at 22:17
The sentence just above the three figures is unfinished. – Hugh Thomas Jan 28 '14 at 23:01
It looks to me like the final configuration is locked - there is no motion of the six cylinders where they remain attached to the sphere other than rotations. If one could prove this, it would obviously negatively answer the second question. – Will Sawin Jan 29 '14 at 4:13
@JamesCranch: Will Sawin says "looks to me", you are not convinced. I have the same two (mixed) feelings, and there is no contradiction. – Wlodek Kuperberg Jan 29 '14 at 16:15
I agree! I can't back up my intuition either: I've just tried doing it with pens, and learned only that I cannot manipulate six pens simultaneously. – James Cranch Jan 29 '14 at 16:22

Here is an idea. Consider the following parameterization, which is supposed to cover the configuration space in question.

$$\mathcal{C}_7:=\left\{\pmatrix{x_k\\y_x\\z_k},\pmatrix{a_k\\b_k\\c_k}_{1\leq k\leq 7}\in{\mathbb{R}^{3\times 2}}^7\,\middle |\, \text{such that conditions 1.-4. are satisfied} \right\}$$

Conditions:

1. $x_k^2+y_k^2+z_k^2=1$
2. $\left\langle\pmatrix{x_k\\y_k\\z_k},\pmatrix{a_k\\b_k\\c_k} \right\rangle=0$
3. $a_k^2+b_k^2+c_k^2=1$
4. $d(l_i,l_j)\geq 2$ for $1\leq i<j\leq 7,$ where we define the line $$l_k:=\left\{2\pmatrix{x_k\\y_k\\z_k}+\alpha\pmatrix{a_k\\b_k\\c_k}\,\middle|\,\alpha\in\mathbb{R} \right\}$$ and denote with $d(\cdot,\cdot)$ the distance between two lines.

Note that condition 4. can be rewritten as polynomial inequalities. Hence $\mathcal{C}_7$ is a semi-algebraic set in $\mathbb{R}^{42}$.

The $(x,z,y)$ are the points, where the unit cylinder is tangent to the unit sphere. The corresponding $(a,b,c)$ gives the direction in the tangent space and the lines $l$ are the cores of the cylinders. (Note that $(-a,-b,-c)$ gives the same cylinder.)

The question "Is $\mathcal{C}_7$ empty?" should be decidable. Maybe an algorithmic approach could help from here.

For the other questions the study of an analogues defined $\mathcal{C}_6$, which we know to be non-empty might be worthwhile.

I wrote a little program that tries to find points in the described semi-algebraic sets. Here's what it found for $\mathcal{C}_6$ (click here for an animation).

Let's take a slightly different point of view. Fix the radius of the ball to be $1$, but let the radii of the $k$ cylinders vary while making sure all cylinders have the same radius. We can then ask: What is the largest radius $r_k$, so that we can find $k$ non-overlapping cylinders of radius $r_k$, that touch the unit ball? Hence the question is: $r_7\geq 1?$

An obvious lower bound on $r_k$ comes from the packing that allows a equatorial section which is a circle packing, as for $k=6$ in figure 1 and figure 2 in the question post. We therefore have: $$r_k\geq \frac{\operatorname{sin}(\frac{\pi}{k})}{1-\operatorname{sin}(\frac{\pi}{k})}$$ Here's a list of decimal approximations for small $k$s: $$\begin{array}{c|cccccc}k&3&4&5&6&7&8\\\hline \frac{\operatorname{sin}(\frac{\pi}{k})}{1-\operatorname{sin}(\frac{\pi}{k})} &6.464101& 2.414213& 1.425919& 1& 0.766421& 0.619914\end{array}$$ A perhaps surprising result of my calculations is the fact that $r_6>1$, indeed $$r_6> 1.04965$$ So in other words there is configuration of $6$ cylinders where the cylinders have radius larger than $1.04965$. Here is a picture of the configuration (again click here for an animation):

I also drew cylinders of radius $1$ with the same tangent points, so one can see the difference.

The configuration space can be viewed as subset of the the $6$th power of the unit tangent bundle of the sphere $(T^1(S^2))^6$ (see conditions 1.-4. and Henrik Rüping's comment).

The upshot of finding a configuration with larger radius is: the configuration space contains an open subset of $(T^1(S^2))^6$ and hence is $18$-dimensional locally.

Edit:

Here is list of lower bounds on $r_k$ for small $k$:

• For $k=3$ and $k=4$ I conjecture the trivial bound for $r_k$ given above to be sharp.
• For $k=5$ one can find a configuration that shows: $r_5>1.45289>1.425919$
• For $k=6$ we have $r_6>1.04965 >1$ as mentioned above.
• For $k=7$ I found a configuration that shows $r_7>0.846934>0.766421$. Here is a picture of this configuration (again click here for an animation):

-
I do not understand, why you need condition (3). I would just normalize the tangent vector $(a_k,b_k,c_k)$ instead. – HenrikRüping Apr 1 '14 at 8:26
Furthermore if we drop condition (4), we would just get a manifold (the 6-th power of the unit tangent bundle of the sphere $T^1(S^2)^6$). So in order to see that Figure (3) is an isolated point, one could compute the differentials of the polynomial functions appearing in (4) at that point. – HenrikRüping Apr 1 '14 at 8:31
Nice idea, fantastic graphics! – Wlodek Kuperberg Apr 2 '14 at 0:58
What a marvelous surprise! The configuration of $6$ cylinders with radius exceeding $1.04965$ is astounding! – Wlodek Kuperberg Apr 3 '14 at 0:54
I doubt that I can get a better answer any time soon, therefore I am awarding the bounty to Moritz Firsching. Thank you, Moritz! – Wlodek Kuperberg Apr 4 '14 at 1:51

This is not a complete answer, but a suggestion of approach to prove that the configuration shown in figure 3 is locked. I hope it is not to naive.

We consider a continuous perturbation of the configuration and want to prove it is obtained by applying a continuous deformation of identity in $\mathrm{SO}(3)$.

Step 1: look at two opposite cylinders, and show that their contact points with the sphere must stay antipodal. This should hold because otherwise one of the other four cylinders would probably not have enough room left.

Step 2: consider again two opposite cylinders, and show that they stay parallel. This should hold because of step 1: we can assume that their contact points with the sphere are fixed, and then if they rotate in opposite direction then another pair of opposite cylinders must also rotate in opposite directions, which in turns constrains the movement of the last pair; if I am right, this last pair in turn constrains the first pair to twist in the opposite direction it does twist. In this argument, I guess that the parity of the dimension matters, so the $4$-dimensional version of the problem could have a different solution.

Step 3: conclude the proof. We can assume that a given pair of opposite cylinders is fixed; then the second pair is constrained to rotate in the plane containing its axes (at least at first order), which rotation is prevented by the third pair.

-
Step 1 is crucial, and not obvious at all. I have mixed feelings about it: sometimes I feel it must be that way; sometimes I don't. – Wlodek Kuperberg Mar 31 '14 at 15:56
There is an "invisible" cube circumscribed about the ball in Figure 3; look at the three cylinders "adjacent" to the cube's front-upper-right vertex. Sometimes I think that the configuration of the three cylinders can be "twisted" continuously, so that their points of tangency move closer to the said vertex, allowing for the other three cylinders to twist symmetrically to the ball's center, while all six cylinders remain non-overlapping, but I have no patience for the necessary computations... Maybe someone would like to try a computer experiment...? – Wlodek Kuperberg Mar 31 '14 at 16:10
Consider making six copies of a spherical "2-tile". The bottom layer of the tile is that section of a sphere between the center and 'the closest' cylinder, and the second layer represents the section of the sphere between the center and any point of the same cylinder. Note the first layers remain disjoint, and the second layers can slide over the first layers of a different tile. Now try moving these tiles around on a basketball. Gerhard "Solving Problems Using Analog Computers" Paseman, 2014.03.31 – Gerhard Paseman Mar 31 '14 at 18:16
@WlodekKuperberg: if the two triples of cylinders move symmetrically, then this movement is satisfying step 1. This does not imply that it cannot happen, but that the statement "step 1 => lockedness" would rule out such a movement. – Benoît Kloeckner Mar 31 '14 at 18:17
@BenoîtKloeckner You're right: the points of contact would remain antipodal. But none of the cylinders would remain parallel. So, even if Step 1 were correct, Step 2 could still fail. – Wlodek Kuperberg Mar 31 '14 at 18:48


text:
# Chapter 6.2. Nested Loops – Exam Tasks

In the previous chapter we got familiar with nested loops and to use them drawing different kinds of figures on the console. We learned how to print different size figures, inventing an appropriate logic to construct them using single and nested for loops in combination with various calculations and program logic:

for (int row = 1; row <= 5; row++) {
System.out.print("*");
for (int col = 1; col < 5; col++) {
System.out.print(" *");
}
System.out.println();
}

We also declared our own method repeatStr(…) which helps us to print a given symbol (or a series of characters) certain number of times:

## Exam Tasks

Let's solve several nested loops related exam tasks to practice what we have learned so far and to develop our further algorithmic thinking.

## Task: Drawing a Fort

Write a program that reads from the console an integer n and draws a fortress with width 2 * n columns and height n rows like the examples below. The left and right columns on the inside are n / 2 wide.

### Input Data

The input is an integer n in the range of [3 … 1000].

### Output Data

Print on the console n text rows, depicting the fortress, exactly like the examples.

### Sample Input and Output

Input Output Input Output
3 /^\/^\
|    |
\_/\_/
4 /^^\/^^\
|      |
|      |
\__/\__/
Input Output Input Output
5 /^^\__/^^\
|        |
|        |
|   __   |
\__/  \__/
8 /^^^^\____/^^^^\
|              |
|              |
|              |
|              |
|              |
|     ____     |
\____/    \____/

### Hints and Guidelines

From the task statement we see that the input data will be one line only containing an integer within the range [3 … 1000]. Therefore, we will use a variable of type int.

Once we have declared and initialized the input data, we need to divide the fort into three parts:

• roof
• body
• base

We can see from the examples that the roof is made of two towers and a middle part. Each tower has a beginning /, a middle part ^ and an end \.

 \ is a special symbol in Java. Using it in the System.out.println(…) method, the console will not print it. That's why using \\ we instruct the console that we want to print exactly this symbol, without being interpreted as a special one (it is shielded- this is called “character escaping”).

The size of the middle part is n / 2, therefore we can write this value in a new variable. It will store the size of the middle part of the tower.

Now we declare a second variable, where we will store the value of between the two towers part. The middle roof part has size of 2 * n - 2 * colSize - 4.

In order to print the roof on the console, we will use our repeatStr(…) method, which accepts two parameters (string, int) and concatenate a certain symbol (or series of characters) n times.

The fort body contains a beginning |, a middle part (white space) and an end |. The middle part is a blank space with size of 2 * n – 2. The number of the rows used for walls could be found by the given parameters - n - 3.

In order to draw the last row, which is a part of the base, we need to print the beginning |, the middle part (white space)_(white space) and an end |. To do this, we can use the declared colSize and midSize variables, because we can see from the examples that they are equal to the _ symbol in the roof.

We add to the values of the blank spaces + 1, because we have one blank space more in the examples.

The fort’s base structure is same as the roof one. It is made of two towers and a middle part. Each tower has a beginning \, a middle part _ and an end /.

### Testing in the Judge System

Test your solution here: https://judge.softuni.org/Contests/Practice/Index/658#0.

## Task: Butterfly

Write a program that reads an integer n from the console and draws a butterfly with 2 * n - 1 columns width and 2 * (n - 2) + 1 rows height as in the examples below. Its left and right sides are n – 1 wide.

### Input Data

The input is an integer n in the range of [3 … 1000].

### Output Data

Print 2 * (n - 2) + 1 text lines, representing the butterfly on the console, just like in the examples.

### Sample Input and Output

Input Output Input Output
3 *\ /*
  @
*/ \*
5 ***\ /***
---\ /---
***\ /***
    @
***/ \***
---/ \---
***/ \***
Input Output
7 *****\ /*****
-----\ /-----
*****\ /*****
-----\ /-----
*****\ /*****
      @
*****/ \*****
-----/ \-----
*****/ \*****
-----/ \-----
*****/ \*****

### Hints and Guidelines

From the task statement we see that the input data will be read from only one line, which will contain an integer in the range [3 … 1000]. For this reason, we will use a variable of type int.

We can divide the figure into 3 parts - upper wing , body and lower wing . In order to draw the upper wing, we need to divide it into parts - a beginning *, a middle part \ / and an end *. After looking at the examples we can say that the beginning has size n - 2.

We also see that the upper wing of the butterfly is of size n - 2, so we can make a loop that iterates halfRowSize times.

From the examples we can notice that on an even row we have a beginning -, a middle part \ / and an end *, and on an odd line - a beginning *, a middle part \ / and an end -. Therefore, we need to do an if-else condition to check whether the line is even or odd and print one of the two types of lines accordingly.

To create the body of the butterfly , we can use again the halfRowSize variable and print exactly one line on the console. The body structure has a beginning (white space), a middle @ and an end (white space).

It remains to print the lower wing on the console, which is identical to the upper wing.

### Testing in the Judge System

Test your solution here: https://judge.softuni.org/Contests/Practice/Index/658#1.

## Task: "Stop" Sign

Write a program that reads an integer n from the console and draws a STOP warning sign with size as in the example below.

### Input Data

The input is an integer N in the range of [3 … 1000].

### Output Data

Print text lines on the console depicting the STOP warning sign, just as in the examples below.

### Sample Input and Output

Input Output Input Output
3 ...._______....
...//_____\\...
..//_______\\..
.//_________\\.
//___STOP!___\\
\\___________//
.\\_________//.
..\\_______//..
6 ......._____________.......
......//___________\\......
.....//_____________\\.....
....//_______________\\....
...//_________________\\...
..//___________________\\..
.//_____________________\\.
//_________STOP!_________\\
\\_______________________//
.\\_____________________//.
..\\___________________//..
...\\_________________//...
....\\_______________//....
.....\\\___________//.....
Input Output
7 ........_______________........
.......//_____________\\.......
......//_______________\\......
.....//_________________\\.....
....//___________________\\....
...//_____________________\\...
..//_______________________\\..
.//_________________________\\.
//___________STOP!___________\\
\\___________________________//
.\\_________________________//.
..\\_______________________//..
...\\_____________________//...
....\\___________________//....
.....\\_________________//.....
......\\_______________//......

### Hints and Guidelines

From the task statement we see that the input data will be read from only one line which contains an integer in the range of [3 … 1000]. Therefore, we will use a variable of type int.

We can divide the figure into 3 parts - upper, middle and lower. The upper part consists of two sub-parts - an initial line and lines in which the character expands. The start row is composed of a beginning ., a middle part _ and an end .. After looking at the examples we can say that the beginning is of size n + 1 and it is better to to separate this value into a separate variable.

We need to create a second variable in which we will store the value of the middle of the initial row and is of size 2 * n + 1.

Once we have declared and initialized the two variables, we can print the start line to the console. Let's not forget to pass a new line to the console with System.out.println(…).

In order to draw the lines where the sign is getting "wider", we have to create a loop, that iterates n number of times. The structure of a line consists of a beginning ., // + middle part _ + \\ and an end .. In order to be able to reuse the created variables , we need to decrease the dots by 1 and the underscores by 2, because we have already printed the first row, and the dots and underscores in the next line of the figure decrease.

At each subsequent iteration the beginning and the end decreasing with 1, and the middle part increases by 2.

The middle part of the figure has a beginning // + _, a middle part STOP! and an end _ + \\. The count of the underscores _ is (underscores - 5) / 2.

The lower part of the figure where the sign decreases, can be done by creating a loop again, which iterates n number of times. The structure of a single line is a beginning . + \\, a middle part _ and an end // + .. The number of the dots in the first iteration of the loop should be 0 and increases by one on each subsequent iteration. Therefore, we can say that the size of the dots in the lower part of the figure is equal to i.

For our program to work properly, we need to reduce the number of i by 2 at each iteration of the loop.

### Testing in the Judge System

Test your solution here: https://judge.softuni.org/Contests/Practice/Index/658#2.

## Task: Arrow

Write a program that reads an odd integer n from the console and draws a vertical arrow pointing down, with dimensions as in the examples below.

### Input Data

The input is an odd integer number n in the range of [3 … 79].

### Output Data

Print a vertical arrow on the console with "#" (hash) outlining the arrow and "." outlining the rest.

### Sample Input and Output

Input Output Input Output
3 .###.
.#.#.
##.##
.#.#.
..#..
5 ..#####..
..#...#..
..#...#..
..#...#..
###...###
.#.....#.
..#...#..
...#.#...
....#....
Input Output
9 ....#########....
....#.......#....
....#.......#....
....#.......#....
....#.......#....
....#.......#....
....#.......#....
....#.......#....
#####.......#####
.#.............#.
..#...........#..
...#.........#...
....#.......#....
.....#.....#.....
......#...#......
.......#.#.......
........#........

### Hints and Guidelines

From the task condition, we see that the input data will be read from only one line which contains an integer in the range of [3 … 79]. Therefore, we will use a variable of type int.

We can divide the figure into 3 parts - upper, middle and lower. The upper part consists of two subparts – the initial row and the arrow body. From the examples we see that the number of the outer dots in the initial row and in the arrow body are (n - 1) / 2. We can store this value in a outerDots variable.

The number of the internal dots in the arrow body is (n - 2). We need to create a variable named innerDots, which will store this value.

We can see from the examples the structure of the initial line. We must use the outerDots and n variables declared and initialized by us to print the starting row. We must remember that we have to move to a new line with System.out.println();.

In order to draw on the arrow's body on the console , we have to create a loop, which iterates n - 2 times.

The middle part of the figure consists of a beginning #, a middle part . and an end #. We see from the examples that the number of the # is equal to outerDots increased by 1 and that is why we can use the same variable again.

To draw the the arrow’s lower part, we need to assign new values to the variables outerDots and innerDots.

The loop, we are going to make must iterates n - 2times and we need to print the last row of the figure separately. On each iteration outerDots increases by 1, and innerDots decreases by 2.

The last row of our figure is made of a beginning ., a middle part # and an end .. The number of the . is equal to outerDots.

### Testing in the Judge System

Test your solution here: https://judge.softuni.org/Contests/Practice/Index/658#3.

## Task: Axe

Write a program that takes as an input an integer n and draws an axe with size as shown below. The axe is 5 * N columns wide.

### Input Data

The input is an integer n in the range of [2..42].

### Output Data

Print on the console an axe, exactly like the examples.

### Sample Input and Output

Input Output Input Output
2 ------**--
------*-*-
*******-*-
------***-
5 ---------------**--------
---------------*-*-------
---------------*--*------
---------------*---*-----
---------------*----*----
****************----*----
****************----*----
---------------*----*----
--------------********---
Input Output
8 ------------------------**--------------
------------------------*-*-------------
------------------------*--*------------
------------------------*---*-----------
------------------------*----*----------
------------------------*-----*---------
------------------------*------*--------
------------------------*-------*-------
*************************-------*-------
*************************-------*-------
*************************-------*-------
*************************-------*-------
------------------------*-------*-------
-----------------------*---------*------
----------------------*-----------*-----
---------------------***************----

### Hints and Guidelines

In order to solve the task, we first need to calculate the dashes on the left, the middle dashes, the dashes on the right and the whole length of the figure.

Once we have declared and initialized the variables, we can begin drawing the figure by starting with the upper part. From the examples, we can figure out the structure of the first row and to create a loop that iterates n number of times. At each iteration of the loop the middle dashes increase by 1, and the dashes on the right decrease by 1.

In order to be able to reuse the created variables when drawing the axe’s handle, we need to decrease the middle dashes by 1, and increase the dashes on the right by 1.

We can draw the handle of the axe by iterating the loop n - 2 times. From the examples we can understand what its structure is.

The lower part of the figure we have to divide into 2 subparts - the head of the axe and the last row of the figure. We will print the axe’s head on the console by creating a loop that repeats n / 2 - 1 number of times. At each iteration the dashes on the left and the dashes on the right decrease by 1, and the middle dashes increase by 2.

For the last row of the figure we can use the three declared and initialized variables leftDashes, middleDashes, rightDashes again.

### Testing in the Judge System

Test your solution here: https://judge.softuni.org/Contests/Practice/Index/658#4.


text:
# 10 Most Common 6th Grade PSSA Math Questions

Many students are more concerned about math exams than other subjects. The complexity and difficulty of some of the 6th Grade PSSA test materials cause students to lose their morale and their anxiety increase about the 6th Grade PSSA Math test. It is better for your students to use the 6th Grade PSSA test sample questions at the same time as reading the course materials. This will help them to become more familiar with different ways of solving the problem and to revisit the points they have forgotten. So this post provides an opportunity for your students to test their math skills using 10 common questions of the 6th Grade PSSA Math test.

Make sure to follow some of the related links at the bottom of this post to get a better idea of what kind of mathematics questions your students need to practice.

## 10 Sample 6th Grade PSSA Math Practice Questions

1- What is the equation of a line that passes through points $$(0, 4)$$ and $$(2, 8)$$?

A. $$y = x$$

B. $$y = x + 4$$

C. $$y = 2x + 4$$

D. $$y = 2x – 4$$

2- What is the volume of a box with the following dimensions?

Height $$= 6$$ cm , Width $$= 7$$ cm, Length $$= 9$$ cm

A. $$63 \space cm^3$$

B. $$126\space cm^3$$

C. $$189\space cm^3$$

D. $$378\space cm^3$$

3- Anita’s trick–or–treat bag contains 14 pieces of chocolate, 15 suckers, 16 pieces of gum, 20 pieces of licorice. If she randomly pulls a piece of candy from her bag, what is the probability of her pulling out a piece of sucker?

A. $$\frac{1}{13}$$

B. $$\frac{3}{13}$$

C. $$\frac{14}{65}$$

D. $$\frac{16}{65}$$

4-

In the following rectangle, which statement is false?

A. AD is parallel to BC

B. The measure of the sum of all the angles equals $$360^\circ$$.

C. Length of AB equal to length DC.

D. AB is perpendicular to AC.

5- The area of a rectangular yard is 90 square meters. What is its width if its length is 15 meters?

A. 10 meters

B. 8 meters

C. 6 meters

D. 4 meters

6- Which statement about 4 multiplied by $$\frac{3}{5}$$ must be true?

A. The product is between 1 and 2

B. The product is greater than 3

C. The product is equal to $$\frac{75}{31}$$

D. The product is between 2 and 2.5

7- Which of the following lists shows the fractions in order from least to greatest?
$$\frac{3}{4}, \frac{2}{7}, \frac{3}{8} , \frac{5}{11}$$

A. $$\frac{3}{8}, \frac{2}{7}, \frac{3}{4}, \frac{5}{11}$$

B. $$\frac{2}{7}, \frac{5}{11}, \frac{3}{8}, \frac{3}{4}$$

C. $$\frac{2}{7}, \frac{3}{8}, \frac{5}{11}, \frac{3}{4}$$

D. $$\frac{3}{8}, \frac{2}{7}, \frac{5}{11}, \frac{3}{4}$$

8- A car costing \$300 is discounted $$10\%$$. Which of the following expressions can be used to find the selling price of the car?

A. $$(300)(0.4)$$

B. $$300-(300×0.1)$$

C. $$(300)(0.1)$$

D. $$300-(300×0.9)$$

9- What is the missing price factor of number 420?
$$420=2^2×3^1×…$$

A. $$2^2×3^1×5^1×7^1$$

B. $$2^2×3^1×7^1×9^1$$

C. $$1^2×2^3×2^1×3^1$$

D. $$3^2×5^1×7^1×9^1$$

10- If the area of the following trapezoid is equal to A, which equation represent $$x$$?

A. $$x = \frac{13}{A}$$

B. $$x = \frac{A}{13}$$

C. $$x=A+13$$

D. $$x=A-13$$

## Answers:

1- C
The slope of the line is:
$$\frac{y_2-y_1}{x_2-x_1 }= \frac{8 – 4}{2 – 0}=\frac{4}{2}=2$$
The equation of a line can be written as:
$$y-y_0=m(x – x_0 )→y-4 = 2(x – 0)→y-4 = 2x→y = 2x + 4$$

2- D
Volume of a $$box = length × width × height = 6 × 7 × 9 = 378$$

3- B
$$Probability = \frac{number \space of \space desired \space outcomes}{number \space of \space total \space outcomes}=\frac{15}{14+15+16+20}= \frac{15}{65}=\frac{3}{13}$$

4- D
In any rectangle, sides are not perpendicular to diagonals.

5- C
Let y be the width of the rectangle. Then; $$15×y=90→y=\frac{90}{15}=6$$

6- D
$$4×\frac{3}{5}=\frac{12}{5}=2.4$$
$$2.4>2$$
$$2.4<3$$
$$\frac{75}{31}=2.419≠2.4$$
$$2<2.4<2.5$$ This is the answer!

7- C
Let’s compare each fraction:
$$\frac{2}{7}< \frac{3}{8}< \frac{5}{11} < \frac{3}{4}$$
Only choice C provides the right order.

8- B
To find the discount, multiply the number ($$100\%$$- rate of discount)
Therefore; $$300(100\%-10\%)=300(1-0.1)=300-(300×0.1)$$

9- A
$$420=2^2×3^1×5^1×7^1$$

10- B

The area of the trapezoid is: area= $$\frac{(base 1+base 2)}{2}×height= (\frac{10 + 16}{2})x = A$$
$$→13x = A→x = \frac{A}{13}$$

Looking for the best resource to help you succeed on the Grade 6 PSSA Math test?

21% OFF

X

## How Does It Work?

### 1. Find eBooks

Locate the eBook you wish to purchase by searching for the test or title.

### 2. Add to Cart

Add the eBook to your cart.

### 3. Checkout

Complete the quick and easy checkout process.

### 4. Download

Immediately receive the download link and get the eBook in PDF format.

## Why Buy eBook From Effortlessmath?

Save up to 70% compared to print

Instantly download and access your eBook

Help save the environment

Lifetime access to your eBook

Over 2,000 Test Prep titles available

Over 80,000 happy customers

Over 10,000 reviews with an average rating of 4.5 out of 5

24/7 support

Anytime, Anywhere Access


text:
Tip: You can open any file by its name when you type Ctrl+P (Quick Open).

When you are working on a task, you will find yourself quickly jumping between the same set of files. You can use two powerful commands to navigate in and across files with easy-to-use key bindings.

Hold Ctrl and press Tab to view a list of all files open in an editor group. To open one of these files, use Tab again to pick the file you want to navigate to, then release Ctrl to open it.

Alternatively, you can use Alt+Left and Alt+Right to navigate between files and edit locations. If you are jumping around between different lines of the same file, these shortcuts allow you to navigate between those locations easily.

## Go to Definition

You can go to the definition of a symbol by pressing F12.

If you press Ctrl and hover over a symbol, a preview of the declaration will appear:

Tip: You can jump to the definition with Ctrl+Click or open the definition to the side with Ctrl+Alt+Click.

## Go to Symbols

You can navigate symbols inside a file with Ctrl+Shift+O. By typing : the symbols will be grouped by category. Press Up or Down and navigate to the place you want.

## Open Symbol by Name

You can open a particular symbol by its name with Ctrl+T, regardless of which file contains it. Type the name of a symbol you want to navigate to, and press Enter


text:
zbMATH — the first resource for mathematics

Homogeneous feedback controls for homogeneous systems. (English) Zbl 0877.93088
Summary: Let $$X(x)=\sum ^{n}_{j=2}a_{j}(x)\partial /\partial x_{j}$$ be a real analytic, n-dimensional vector field with $$X(0)=0$$ which is homogeneous of degree $$m\leq 0$$ with respect to a dilation $$\delta ^{r}_{\varepsilon}x= (\varepsilon ^{r_{1}}x_{1},\ldots,\varepsilon ^{r_{n}}x_{n})$$ and $$Y=\partial /\partial x_{1}$$. We show that if the control system $$\dot x=X(x)+uY$$ admits a continuous, asymptotically stabilizing, feedback control $$u(x)$$, then a one-dimensional dynamic extension of the system admits a homogeneous, asymptotically stabilizing (dynamic) feedback control $$\hat u(\tau,x)$$ such that the vector field $\hat W(\tau,x)=\alpha \tau^{1-m}\partial /\partial\tau+ \hat u(\tau,x)\partial /\partial x_{1}+\sum ^{n}_{j=2}a_{j}(x)\partial /\partial x_{j}$ describing the extended, controlled, system is homogeneous of degree m with respect to the extended dilation $\hat\delta^{r}_{\varepsilon}(\tau,x)= (\varepsilon\tau,\varepsilon^{r_{1}}x_{1},\ldots, \varepsilon^{r_{n}}x_{n}).$

MSC:
 93D15 Stabilization of systems by feedback
Full Text:
References:
 [1] Brockett, R.W, Asymptotic stability and feedback stabilization, (), 181-191 · Zbl 0528.93051 [2] Coron, J.M, A necessary condition for feedback stabilization, Systems control lett., 14, 227-232, (1990) · Zbl 0699.93075 [3] W.P. Dayawansa, C.F. Martin and S. Samelson, Asymptotic stabilization of a generic class of three-dimensional homogeneous quadratic systems, preprint. · Zbl 0877.93090 [4] Hermes, H, Asymptotically stabilizing feedback controls, J. differential equations, 92, 76-89, (1991) · Zbl 0736.93069 [5] Hermes, H, Asymptotically stabilizing feedback controls and the nonlinear regulator problem, SIAM J. control optim., 29, 185-196, (1991) · Zbl 0738.93061 [6] Hermes, H, Nilpotent and high order approximations of vector field systems, SIAM rev., 33, 238-264, (1991) · Zbl 0733.93062 [7] Hermes, H, Homogeneous coordinates and continuous asymptotically stabilizing feedback controls, (), 249-260 [8] Kawski, M, Stabilization and nilpotent approximations, (), 1244-1248 [9] Kawski, M, Homogeneous stabilizing feedback laws, (), 497-516 [10] Kurzweil, J; Kurzweil, J; Kurzweil, J, On the reversibility of the theorem of Lyapunov concerning the stability of motion, Czechoslovak math. J., Czechoslovak math. J., Czechoslovak math. J., 6, 474-484, (1956), (English summary) · Zbl 0127.30702 [11] Rosier, L, Homogeneous Lyapunov functions for homogeneous vector fields, Systems control lett., 19, 467-473, (1992) · Zbl 0762.34032 [12] Wilson, F.W, The structure of the level surfaces of a Lyapunov function, J. differential equations, 4, 323-329, (1967) · Zbl 0152.28701
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
# What is a buffer attribute in JSP?

JSPJava 8Object Oriented ProgrammingProgramming

#### Jakarta EE/Java JEE 8 Web Development(Servlet, JSP and JDBC)

48 Lectures 4 hours

The buffer attribute specifies the buffering characteristics for the server output response object.

You may code a value of "none" to specify no buffering so that the servlet output is immediately directed to the response object or you may code a maximum buffer size in kilobytes, which directs the servlet to write to the buffer before writing to the response object.

To direct the servlet to write the output directly to the response output object, use the following −

<%@ page buffer = "none" %>

Use the following to direct the servlet to write the output to a buffer of size not less than 8 kilobytes −

<%@ page buffer = "8kb" %>
Updated on 30-Jul-2019 22:30:25


text:
# What does the exclamation mark do?

I've seen this but never knew what it does. Can any one let me in on the details? Thanks.

-
One of my students: "What is $7!$... is it like SEVEN?!?!" –  The Chaz 2.0 Sep 27 '11 at 2:27
@TheChaz: in a high squeaky voice? ;) –  Ｊ. Ｍ. Sep 28 '11 at 18:15
@J. M. - Not exactly! He was actually one of the bigger college students that I've worked with... I used to run into Thomas at the gym every so often. –  The Chaz 2.0 Sep 28 '11 at 19:52
"Among the worst of barabarisms is that of introducing symbols which are quite new in mathematical, but perfectly understood in common, language. Writers have borrowed from the Germans the abbreviation n! to signify 1.2.3.(n - 1).n, which gives their pages the appearance of expressing surprise and admiration that 2, 3, 4, &c. should be found in mathematical results." - Augustus de Morgan, 1842. –  Michael Lugo Nov 10 '11 at 15:51

Probably you're thinking about the symbol for the factorial function: $$n! = 1\times 2 \times 3\times \cdots \times (n-1) \times n$$

-

An exclamation mark can also be shorthand for "unique". For example, the statement $$\forall y\in f(A), \exists!x\in A \text{ s.t. } y=f(x)$$ would be read as "for all $y$ in the range of $f$, there exits a unique $x$ in the domain such that $y=f(x)$". In other words, $f$ is one-to-one.

-

...or possibly double factorial $n!! = n \times (n-2) \times (n-4) \times \cdots$, or maybe subfactorial, $!n$, also known as derangement number.

Added ... and superfactorial for desert.

-
the superfactorial has little rainfall? :-) –  robjohn Sep 27 '11 at 1:28
...and there's even a hyperfactorial, too. :) –  Ｊ. Ｍ. Sep 28 '11 at 18:14

For completeness:

Although in mathematics the $!$ almost always refers to the factorial function, you often see it in quasi-mathematical contexts with a different meaning.

For example, in many programming languages it is used to mean negation, for example in Java the expression !true evaluates to false. It is also commonly used to express inequality, for example in the expression 1 != 2, read as '1 is not equal to 2'.

It is also used in some functional languages to denote a function that modifies its input, as in the function set! in Scheme, which sets its first argument to the value of its second argument.

-

I just wanted to add a common usage for it as well since that may be of more interest to you.

A common usage for the factorial is in permutations.

For example: If there were 3 people in a race, how many possible ways could there be to arrange the ranking.

The answer would be 3! (3 factorial) or 3 x 2 x 1 or 6 ways.

Listing them the brute force way: 1) A,B,C

2)A,C,B

3)B,A,C

4)B,C,A

5)C,A,B

6)C,B,A

This extends into a lot of other things but most commonly associated with statistics, I believe.

-


text:
Browse Questions

# Moment of inertia of a thin rod of mass M and length l about an axis as shown .

$\begin {array} {1 1} (a)\;\frac{Ml^2 \sin \theta}{12} & \quad (b)\;\frac{Ml^2 \cos \theta}{12} \\ (c)\;\frac{Ml^2}{12} & \quad (d)\;\frac{Ml^2}{3} \end {array}$

Man per unit length $= \large\frac{M}{l}$
Consider an element of width dx at a distance x from 0
mass of element $=dm= \large\frac{M}{2}$$dx$
M.I= man $\times$ perpendicular distance from axis of rotation
Hence $\large\frac{Ml^2 \sin \theta}{12}$ is a correct answer.
edited Jun 18, 2014


text:
# Using output of NDSolve in further NDSolve calculations [closed]

I am trying to use the interpolating functions found using NDSolve to solve a further differential equation where the first solutions depend on two arbitrary parameters.

As a simple example, suppose I have two coupled ODES that I can write as:

func[r_,u_]:=y''[x] == u*y'[x]+r^2*y[x]*x^3
sol[r_,u_]:= NDSolve[{func[r,u],y[0]==r,y'[0]==r*u},y,{x,0,50}]
func2[r_,u_]:= (z''[x]==y'[x]*r+u*y[x]*z'[x])/.sol[r,u]
sol2[r_,u_]:= NDSolve[{func2[r,u],z[0]==1,z'[0]==0},z,{x,0,50}]

The problem is that I get the error message when running the fourth line telling me that replacing y[x] etc. is not a good replacement rule.

In reality, my system is a horrible non-linear set f coupled ODEs with one final equation that depends on the solutions of the others. Furthermore, r and u also control the boundary conditions but I think this example suffices because I think the problems are caused by the fact that there is r and u dependence in the ODE.

I can see many posts where the output of NDSolve does not depend on any parameters, in which case it seems trivial to just define a function that does what I want e.g.

f1[x_]:=Evaluate[First[y[x]/.NDSolve[{y[x]''+y[x]'+x^3==0,y[0]==1,y'[0]==0},y,{x,0,50}]]]

sol=NDSolve[{z'[x]==^3*y[x]+y'[x],z[0]=0},z,{x,0,50}]

would work if it were not for u.

I am also aware that I can solve both equations simultaneously but the second equation is stiff so I would like to use a different method for it. Actually, the first set are DAE's whilst the last one is not so splitting the two would help me a lot.

## closed as unclear what you're asking by Michael E2, m_goldberg, MarcoB, ubpdqn, Yves KlettAug 3 '16 at 5:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• How are you calling the function? – Feyre Aug 1 '16 at 15:29
• Welcome! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour and check the faqs! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! – user9660 Aug 1 '16 at 15:33
• – user9660 Aug 1 '16 at 15:34
• Thanks for the help guys. I actually wrote this code in by hand because my actual code is a lot more complicated and my real ODE is very long. Feyre, what do you mean how and I calling the function? – jsaxon Aug 1 '16 at 15:41
• sol2[r_,u_]:=  is set delayed, so I assume you are calling it in some form of sol2[1,2] – Feyre Aug 1 '16 at 16:09

Well, I made some changes, but then realized I hadn't changed anything important. I shortened the integration to {x, 0, 2} to save time. The original code works with this change. I memoized sol so that it's computed only once for each {r, u}. You stick First@ on NDSolve[] to remove a set of braces, but it's not important.

Clear[func, func2, sol, sol2, x, y, r, u];

func[r_, u_] := y''[x] == u*y'[x] + r^2*y[x]*x^3;
sol[r_?NumericQ, u_?NumericQ] :=
sol[r, u] = (* saves the value so that it is computed once *)
NDSolve[{func[r, u], y[0] == r, y'[0] == r*u}, y, {x, 0, 2},
InterpolationOrder -> All]
func2[r_?NumericQ, u_?NumericQ] := (z''[x] == y'[x]*r + u*y[x]*z'[x]) /. sol[r, u]
sol2[r_, u_] := NDSolve[{func2[r, u], z[0] == 1, z'[0] == 0}, z, {x, 0, 2}]

sol2[2, 1]


text:
## QAWS adaptive integration for singular functions

The QAWS algorithm is designed for integrands with algebraic-logarithmic singularities at the end-points of an integration region. In order to work efficiently the algorithm requires a precomputed table of Chebyschev moments.

Function: gsl_integration_qaws_table * gsl_integration_qaws_table_alloc (double alpha, double beta, int mu, int nu)

This function allocates space for a gsl_integration_qaws_table struct and associated workspace describing a singular weight function @math{W(x)} with the parameters @math{(\alpha, \beta, \mu, \nu)},

where @math{\alpha < -1}, @math{\beta < -1}, and @math{\mu = 0, 1}, @math{\nu = 0, 1}. The weight function can take four different forms depending on the values of @math{\mu} and @math{\nu},

The singular points @math{(a,b)} do not have to be specified until the integral is computed, where they are the endpoints of the integration range.

The function returns a pointer to the newly allocated gsl_integration_qaws_table if no errors were detected, and 0 in the case of error.

Function: int gsl_integration_qaws_table_set (gsl_integration_qaws_table * t, double alpha, double beta, int mu, int nu)
This function modifies the parameters @math{(\alpha, \beta, \mu, \nu)} of an existing gsl_integration_qaws_table struct t.

Function: void gsl_integration_qaws_table_free (gsl_integration_qaws_table * t)
This function frees all the memory associated with the gsl_integration_qaws_table struct t.

Function: int gsl_integration_qaws (gsl_function * f, const double a, const double b, gsl_integration_qaws_table * t, const double epsabs, const double epsrel, const size_t limit, gsl_integration_workspace * workspace, double *result, double *abserr)

This function computes the integral of the function @math{f(x)} over the interval @math{(a,b)} with the singular weight function @math{(x-a)^\alpha (b-x)^\beta \log^\mu (x-a) \log^\nu (b-x)}. The parameters of the weight function @math{(\alpha, \beta, \mu, \nu)} are taken from the table t. The integral is,

The adaptive bisection algorithm of QAG is used. When a subinterval contains one of the endpoints then a special 25-point modified Clenshaw-Curtis rule is used to control the singularities. For subintervals which do not include the endpoints an ordinary 15-point Gauss-Kronrod integration rule is used.


text:
Formats
Format
BibTeX
MARC
MARCXML
DublinCore
EndNote
NLM
RefWorks
RIS

### Abstract

This study examines the impacts of the Margin Protection Program for Dairy Producers (MPP-Dairy) on the effective margins realized by dairy producers in various regions. The effects are examined for each selected margin ($4.00-$8.00 in \$0.50 increments), and each percentage of production history (25%-90% in 5% increments). The “effective margins” are the regions’ actual margins as a function of their milk and feed prices having been added to the national net at each respective coverage level. The analysis simulated couplet margins for fifteen regions from 2017-2020. The results show that more than half of the regions have higher probabilities of triggering indemnities at every coverage level compared to the national. This means that if a regional policy of similar construction were available to producers, it might pay out more frequently. This study did find that the margin volatility was reduced over the whole period when the policy effects were accounted for.


text:
2003-locality

Summary

Karlton Sequeira, Mohammed J. Zaki and Boleslaw Szymanski, Improving Spatial Locality using Data Mining. In 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Aug 2003. (PDF) #2003-localityBib

Bibtex entry

@INPROCEEDINGS { 2003-locality,    AUTHOR = { Karlton Sequeira and Mohammed J. Zaki and Boleslaw Szymanski },    TITLE = { Improving Spatial Locality using Data Mining },    BOOKTITLE = { 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining },    MONTH = { Aug },    YEAR = { 2003 },    PDF = { SIGKDD03-spatial.pdf },    KEYWORD = { Conference,DataMining,Systems },}


text:
1. ## subgroup generated

Let $S$ be a proper subgroup of $G$. If $G-S$ is the complement of $S$, prove that $=G$.

Let $S$ be a proper subgroup of $G$. If $G-S$ is the complement of $S$, prove that $=G$.
clearly $ \subseteq G.$ now let $g \in G.$ if $g \in G - S,$ then $g \in .$ if $g \in S,$ then choose $x \in G-S.$ then $x^{-1} \in G-S$ and $gx=y \in G-S.$ so: $g=yx^{-1} \in .$ Q.E.D.